Navegar

Colección

Datos Estadísticas

Artículo

Castano, J.M. "A parsing approach to SAT" (2014) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8864:3-14
El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We present a parsing approach to address the problem of propositional satisfiability (SAT). We use a very simple translation from formulae in conjunctive normal form (CNF) to strings to be parsed by an Earley type algorithm. The parsing approach enables both a SAT and an ALL-SAT solver. The parsing algorithm is based in a model of automata that uses multiple stacks, presented here with a grammar characterization. The time complexity of the algorithm is polynomial, where the degree of the polynomial is dependent on the number of stacks used. It is not dependent on the length of the input nor properties of the grammar. However the number of stacks used might be a function on the number of variables and this is an open question. The number of stacks effectively used in practice is dependent on ordering of variables and clauses. A prototype of the parser was implemented and tested. © Springer International Publishing Switzerland 2014.

Registro:

Documento: Artículo
Título:A parsing approach to SAT
Autor:Castano, J.M.
Filiación:Depto. de Computación, FCEyN, UBA, Buenos Aires, Argentina
Palabras clave:ALL-SAT; Earley parsing; Multi-stack automata; SAT; Automata theory; Boolean algebra; Boolean functions; Computational complexity; Formal logic; ALL-SAT; Conjunctive normal forms; Earley parsing; Multi-stack automata; Order of variables; Parsing algorithm; Propositional satisfiability; SAT; Formal languages
Año:2014
Volumen:8864
Página de inicio:3
Página de fin:14
DOI: http://dx.doi.org/10.1007/978-3-319-12027-0_1
Título revista:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8864_n_p3_Castano

Referencias:

  • Barton, G.E., Computational complexity in two-level morphology (1986) Proc. of the 24th ACL, pp. 53-59. , New York
  • Biere, A., Heule, M., van Maaren, H., Walsh, T., (2009) Handbook of Satisfiability, , IOS Press
  • Büchi, J.R., Weak second-order arithmetic and finite automata (1960) Zeit. Math. Logik. Grund. Math, pp. 66-92
  • Castaño, J., Global index grammars and descriptive power (2004) Journal of Logic, Language and Information, 13, pp. 403-419
  • Cherubini, A., Breveglieri, L., Citrini, C., Reghizzi, S., Multipushdown languages and grammars (1996) International Journal of Foundations of Computer Science, 7 (3), pp. 253-292
  • Dassow, J., Păun, G., Salomaa, A., Grammars with controlled derivations (1997) Handbook of Formal Languages, 2. , Springer, Berlin
  • Earley, J., An Efficient Context-free Parsing Algorithm (1970) Communications of the ACM, 13, pp. 94-102
  • Elgot, C.C., (1961) Decision problems of automata design and related arithmetics, , Transactions of the American Mathematical Society
  • Gómez-Rodríguez, C., Kuhlmann, M., Satta, G., Efficient parsing of well-nested linear context-free rewriting systems (2010) Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 276-284. , HLT 2010,. Association for Computational Linguistics, Stroudsburg
  • Khabbaz, N.A., A geometric hierarchy of languages (1974) Journal of Computer and System Sciences, 8 (2), pp. 142-157
  • Neuhaus, P., Broker, N., The complexity of recognition of linguistically adequate dependency grammars (1997) Proceedings of the 35th AnnualMeeting of the Association for Computational Linguistics, pp. 337-343. , Association for Computational Linguistics, Madrid
  • Purdom, P.W., Jr., Brown, C.A., Parsing extended LR(k) grammars (1981) Acta Informatica, 15 (2), pp. 115-127
  • Ristad, E.S., Computational complexity of current GPSG theory (1986) Proc. of the 24th ACL, pp. 30-39. , New York
  • Satta, G., Recognition of Linear Context-Free Rewriting Systems (1992) ACL, pp. 89-95
  • Satta, G., Some computational complexity results for synchronous context-free grammars (2005) Proceedings of HLT/EMNLP 2005, pp. 803-810
  • Seki, H., Matsumura, T., Fujii, M., Kasami, T., On multiple context-free grammars (1991) Theoretical Computer. Science, pp. 191-229
  • Shieber, S., Schabes, Y., Pereira, F., Principles and implementation of deductive parsing (1995) Journal of Logic Programming, 24, pp. 3-36
  • Sikkel, K., (1997) Parsing schemata, , Springer
  • Tomita, M., An efficiente augmented-context-free parsing algorithm (1987) Computational Linguistics, 13, pp. 31-46
  • La Torre, S., Madhusudan, P., Parlato, G., A robust class of context-sensitive languages (2007) LICS, pp. 161-170. , IEEE Computer Society
  • Vardi, M.Y., Logic and Automata: A Match Made in Heaven (2003) ICALP 2003. LNCS, 2719, pp. 64-65. , Springer, Heidelberg
  • Vardi, M.Y., Wolper, P., Automata-theoretic techniques for modal logics of programs (1986) J. Comput. Syst. Sci, 32, pp. 183-221
  • Wartena, C., Storage products and linear control of derivations (2008) Theory of Computing Systems, 42 (2), pp. 157-186
  • Weir, D., A geometric hierarchy beyond context-free languages (1992) Theoretical Computer Science, 104 (2), pp. 235-261

Citas:

---------- APA ----------
(2014) . A parsing approach to SAT. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8864, 3-14.
http://dx.doi.org/10.1007/978-3-319-12027-0_1
---------- CHICAGO ----------
Castano, J.M. "A parsing approach to SAT" . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8864 (2014) : 3-14.
http://dx.doi.org/10.1007/978-3-319-12027-0_1
---------- MLA ----------
Castano, J.M. "A parsing approach to SAT" . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8864, 2014, pp. 3-14.
http://dx.doi.org/10.1007/978-3-319-12027-0_1
---------- VANCOUVER ----------
Castano, J.M. A parsing approach to SAT. Lect. Notes Comput. Sci. 2014;8864:3-14.
http://dx.doi.org/10.1007/978-3-319-12027-0_1