Propositional Satisfiability (SAT) as a language problem

We present an approach to propositional satisfiability as a Finite State Automata automata construction problem. From a theoretical point of view it has consequences for languages beyond context free power. There are no consequences on complexity issues due to Automata construction (using intersecti...

Descripción completa

Detalles Bibliográficos
Autores principales: Castaño, Rodrigo, Castaño, José M.
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2011
Materias:
Ciencias Informáticas
ALL-SAT; model counting; FSA intersection; regular expression compilation; Non-clausal formula; clause learning
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/18791
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-18791
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
ALL-SAT; model counting; FSA intersection; regular expression compilation; Non-clausal formula; clause learning
spellingShingle Ciencias Informáticas
ALL-SAT; model counting; FSA intersection; regular expression compilation; Non-clausal formula; clause learning
Castaño, Rodrigo
Castaño, José M.
Propositional Satisfiability (SAT) as a language problem
topic_facet Ciencias Informáticas
ALL-SAT; model counting; FSA intersection; regular expression compilation; Non-clausal formula; clause learning
description We present an approach to propositional satisfiability as a Finite State Automata automata construction problem. From a theoretical point of view it has consequences for languages beyond context free power. There are no consequences on complexity issues due to Automata construction (using intersection) is PSPACE-complete. From a practical point of view it was shown that this approach is competitive with ALL-SAT approaches and even with state of the art SAT solvers on traditional hard problems. Here, we show that techniques used in DPLL can be used in an automata approach. This kind of approach opens a new path of research on propositional satisfiability.
format Objeto de conferencia
Objeto de conferencia
author Castaño, Rodrigo
Castaño, José M.
author_facet Castaño, Rodrigo
Castaño, José M.
author_sort Castaño, Rodrigo
title Propositional Satisfiability (SAT) as a language problem
title_short Propositional Satisfiability (SAT) as a language problem
title_full Propositional Satisfiability (SAT) as a language problem
title_fullStr Propositional Satisfiability (SAT) as a language problem
title_full_unstemmed Propositional Satisfiability (SAT) as a language problem
title_sort propositional satisfiability (sat) as a language problem
publishDate 2011
url http://sedici.unlp.edu.ar/handle/10915/18791
work_keys_str_mv AT castanorodrigo propositionalsatisfiabilitysatasalanguageproblem
AT castanojosem propositionalsatisfiabilitysatasalanguageproblem
bdutipo_str Repositorios
_version_ 1764820463271280642

Ejemplares similares