Abstract
We use a finite state (FSA) construction approach to address the problem of propositional satisfiability (SAT). We use a very simple translation from formulas in conjunctive normal form (CNF) to regular expressions and use regular expressions to construct an FSA. As a consequence of the FSA construction, we obtain an ALL-SAT solver and model counter. We compare how several variable ordering (state ordering) heuristics affect the running time of the FSA construction. We also present a strategy for clause ordering (automata composition). We compare the running time of state-of-the-art model counters, BDD based sat solvers and we show that this FSA approach obtains state-of-the-art performance on some hard unsatisfiable benchmarks. This work brings up many questions on the possible use of automata to address SAT.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aloul, F., Lynce, I., Prestwich, S.: Symmetry Breaking in Local Search for Unsatisfiability. In: 7th International Workshop on Symmetry and Constraint Satisfaction Problems, Providence, RI (2007)
Aloul, F.A., Markov, I.L., Sakallah, K.A.: FORCE: a fast and easy-to-implement variable-ordering heuristic. In: ACM Great Lakes Symposium on VLSI, pp. 116–119. ACM Press, New York (2003)
Aloul, F.A., Ramani, A., Markov, I.L., Sakallah, K.A.: Solving difficult SAT instances in the presence of symmetry. In: DAC, pp. 731–736. ACM Press, New York (2002)
Barton, G.E.: Computational complexity in two-level morphology. In: Proc. of the 24th ACL, New York, pp. 53–59 (1986)
Beesley, K., Karttunen, L.: Finite State Morphology. CSLI Publications (2003)
Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. IOS Press, Amsterdam (2009)
Büchi, J.R.: Weak second-order arithmetic and finite automata. Zeit. Math. Logik. Grund. Math. 66–92 (1960)
Castaño, J.: Two views on crossing dependencies, language, biology and satisfiability. In: 1st International Work-Conference on Linguistics, Biology and Computer Science: Interplays. IOS Press, Amsterdam (2011)
Darwiche, A.: New Advances in Compiling CNF into Decomposable Negation Normal Form. In: ECAI, pp. 328–332 (2004)
Elgot, C.C.: Decision problems of automata design and related arithmetics. Transactions of the American Mathematical Society (1961)
Franco, J., Kouril, M., Schlipf, J., Ward, J., Weaver, S., Dransfield, M.R., Vanfleet, W.M.: SBSAT: a state-based, BDD-based satisfiability solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 398–410. Springer, Heidelberg (2004)
Gomes, C.P., Sabharwal, A., Selman, B.: Model Counting. In: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 633–654. IOS Press, Amsterdam (2009)
Hadzic, T., Hansen, E.R., O’Sullivan, B.: On Automata. In: MDDs and BDDs in Constraint Satisfaction (2008)
Hansen, P., Jaumard, B.: Algorithms for the maximum satisfiability problem. Computing 44, 279–303 (1990)
Lange, K., Rossmanith, P.: The emptiness problem for intersections of regular languages. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol. 629, pp. 346–354. Springer, Heidelberg (1992)
Lewis, H.R., Papadimitriou, C.H.: Elements of the Theory of Computation, 2nd edn. Prentice-Hall, Upper Saddle River (1997)
Marek, V.W.: Introduction to Mathematics of Satisfiability. Chapman and Hall/CRC (2010)
Muise, C., Beck, J.C., McIlraith, S.: Fast d-DNNF Compilation with sharpSAT (2010)
Sinz, C., Biere, A.: Extended resolution proofs for conjoining bDDs. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol. 3967, pp. 600–611. Springer, Heidelberg (2006)
Tapanainen, P.: Applying a Finite-State Intersection Grammar. In: Roche, E., Schabes, Y. (eds.) Finite-State Language Processing, pp. 311–327. MIT Press, Cambridge (1997)
Thurley, M.: sharpSAT – counting models with advanced component caching and implicit BCP. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 424–429. Springer, Heidelberg (2006)
Urquhart, A.: Hard examples for resolution. J. ACM 34(1), 209–219 (1987)
Vardi, M.: Logic and Automata: A Match Made in Heaven. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 193–193. Springer, Heidelberg (2003)
Vardi, M.Y., Wolper, P.: Automata-Theoretic techniques for modal logics of programs. J. Comput. Syst. Sci. 32, 183–221 (1986)
Vempaty, N.R.: Solving Constraint Satisfaction Problems Using Finite State Automata. In: AAAI, pp. 453–458 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Castaño, J.M., Castaño, R. (2011). Variable and Clause Ordering in an FSA Approach to Propositional Satisfiability. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, JM., Maurel, D. (eds) Implementation and Application of Automata. CIAA 2011. Lecture Notes in Computer Science, vol 6807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22256-6_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-22256-6_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22255-9
Online ISBN: 978-3-642-22256-6
eBook Packages: Computer ScienceComputer Science (R0)