On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars

• Autorzy: Jeż A. , Okhotin A.

Identyfikatory

DOI

10.3233/FI-2018-1713

• Języki publikacji: EN

Abstrakty

EN

Unambiguous conjunctive grammars with 1 nonterminal symbol are shown to be strictly weaker than the grammars with 2 nonterminal symbols, which are in turn strictly weaker that the grammars with 3 or more nonterminal symbols. This hierarchy is established by considering grammars over a one-symbol alphabet, for which it is shown that 1-nonterminal grammars describe only regular languages, 2-nonterminal grammars describe some non-regular languages, but all of them are in a certain sense sparse, whereas 3-nonterminal grammars may describe some non-regular languages of non-zero density. It is also proved that one can test a 2-nonterminal grammar for equivalence with a regular language, whereas the equivalence between a pair of 2-nonterminal grammars is undecidable.

Słowa kluczowe

EN

conjunctive grammars; ambiguity; language equations; unary languages; descriptional complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 162, nr 1
• Strony: 43--72
• Opis fizyczny: Bibliogr. 31 poz., rys.

Twórcy

autor

Jeż A.

• Institute of Computer Science, University of Wrocław, Joliot-Curie 15, 50–383 Wroclaw, Poland

autor

Okhotin A.

• St. Petersburg State University, 7/9 Universitetskaya nab., Saint Petersburg 199034, Russia

Bibliografia

• [1] T. Aizikowitz, M. Kaminski, “Conjunctive grammars and alternating pushdown automata”, Acta Informatica, 2013;50(3):175-197. URL http://dx.doi.org/10.1007/978-3-540-69937-8_6.
• [2] T. Aizikowitz, M. Kaminski, “LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata”, Journal of Computer and System Sciences, 2016;82(8):1329-1359. URL http://dx.doi.org/10.1016/j.jcss.2016.05.008.
• [3] J.-P. Allouche, J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.
• [4] F. Baader, A. Okhotin, “On language equations with one-sided concatenation”, Fundamenta Informaticae, 2013;126(1):1-35. URL http://dx.doi.org/10.3233/FI-2013-870.
• [5] N. Blum, “More on the power of chain rules in context-free grammars”, Theoretical Computer Science, 1983;27:287-295. URL http://dx.doi.org/10.1016/0304-3975(82)90122-0.
• [6] J. A. Brzozowski, E. L. Leiss, “On equations for regular languages, finite automata, and sequential networks”, Theoretical Computer Science, 1980;10:19-35. URL http://dx.doi.org/10.1016/0304-3975(80)90069-9.
• [7] K. Culik II, J. Gruska, A. Salomaa, “Systolic trellis automata”, I and II, International Journal of Computer Mathematics, 1984;15:195-212; 1984;16:3-22.
• [8] C. Dyer, “One-way bounded cellular automata”, Information and Control, 1980;44:261-281. URL http://dx.doi.org/10.1016/S0019-9958(80)90164-3.
• [9] J. Gruska, “Descriptional complexity of context-free languages”, Mathematical Foundations of Computer Science (MFCS 1973, Strbské Pleso, High Tatras), Czechoslovakia, 3-8 September 1973, pp. 71-83.
• [10] O. H. Ibarra, S. M. Kim, “Characterizations and computational complexity of systolic trellis automata”, Theoretical Computer Science, 1984;29:123-153. URL http://dx.doi.org/10.1016/0304-3975(84)90015-X.
• [11] A. Jeż, “Conjunctive grammars can generate non-regular unary languages”, International Journal of Foundations of Computer Science, 2008;19:3:597-615. URL http://dx.doi.org/10.1142/S012905410800584X.
• [12] A. Jeż, A. Okhotin, “Conjunctive grammars over a unary alphabet: undecidability and unbounded growth”, Theory of Computing Systems, 2010;46(1):27-58. URL http://dx.doi.org/10.1007/s00224-008-9139-5.
• [13] A. Jeż, A. Okhotin, “Complexity of equations over sets of natural numbers”, Theory of Computing Systems, 2011;48(2):319-342. URL http://dx.doi.org/10.1007/s00224-009-9246-y.
• [14] A. Jeż, A. Okhotin, “One-nonterminal conjunctive grammars over a unary alphabet”, Theory of Computing Systems, 2011;49(2):319-342. URL http://dx.doi.org/10.1007/s00224-011-9319-6.
• [15] A. Jeż, A. Okhotin, “Unambiguous conjunctive grammars over a one-symbol alphabet”, Theoretical Computer Science, 2016;665:13-39. URL http://dx.doi.org/10.1016/j.tcs.2016.12.009.
• [16] K. Kanchan Devi, S. Arumugam, “Probabilistic conjunctive grammar”, Theoretical Computer Science and Discrete Mathematics (ICTCSDM 2016, Krishnankoil, India, December 19-21, 2016), LNCS 10398, pp. 119-127. URL https://doi.org/10.1007/978-3-319-64419-6_16.
• [17] S. Kuznetsov, “Conjunctive grammars in Greibach normal form and the Lambek calculus with additive connectives”, Proceedings of Formal Grammar 2012 and Formal Grammar 2013, LNCS 8036, 2013, pp. 242-249. URL http://dx.doi.org/10.1007/978-3-642-39998-5_15.
• [18] A. Okhotin, “Conjunctive grammars”, Journal of Automata, Languages and Combinatorics, 2001: 6(4):519-535.
• [19] A. Okhotin, “On the equivalence of linear conjunctive grammars to trellis automata”, Informatique Théorique et Applications, 2004;38(1):69-88. URL http://dx.doi.org/10.1051/ita:2004004.
• [20] A. Okhotin, “State complexity of linear conjunctive languages”, Journal of Automata, Languages and Combinatorics, 2004;9(2-3):365-381.
• [21] A. Okhotin, “On the number of nonterminals in linear conjunctive grammars”, Theoretical Computer Science, 2004;320(2-3):419-448. URL http://dx.doi.org/10.1016/j.tcs.2004.03.002.
• [22] A. Okhotin, “Unambiguous Boolean grammars”, Information and Computation, 2008;206:1234-1247. URL http://dx.doi.org/10.1016/j.ic.2008.03.023.
• [23] A. Okhotin, “Conjunctive and Boolean grammars: the true general case of the context-free grammars”, Computer Science Review, 2013;9:27-59. URL http://dx.doi.org/10.1016/j.cosrev.2013.06.001.
• [24] A. Okhotin, C. Reitwießner, “Parsing Boolean grammars over a one-letter alphabet using online convolution”, Theoretical Computer Science, 2012;457:149-157. URL http://dx.doi.org/10.1016/j.tcs.2012.06.032.
• [25] A. Okhotin, P. Rondogiannis, “On the expressive power of univariate equations over sets of natural numbers”, Information and Computation, 2012;212:1-14. URL http://dx.doi.org/10.1016/j.ic.2012.01.004.
• [26] V. Terrier, “On real-time one-way cellular array”, Theoretical Computer Science, 1995;141(1-2):331-335. URL http://dx.doi.org/10.1016/0304-3975(94)00212-2.
• [27] V. Terrier, “Recognition of poly-slender context-free languages by trellis automata”, Theoretical Computer Science, 2017;692:1-24. URL https://doi.org/10.1016/j.tcs.2017.05.041.
• [28] V. Terrier, “Some computational limits of trellis automata”, Cellular Automata and Discrete Complex Systems (AUTOMATA 2017, Milan, Italy, 7-9 June 2017), LNCS 10248, pp. 176-186. URL https://doi.org/10.1007/978-3-319-58631-1_14.
• [29] R. Yoshinaka, “Learning conjunctive grammars and contextual binary feature grammars”, Language and Automata Theory and Applications (LATA 2015), LNCS 8977, pp. 623-635. URL http://dx.doi.org/10.1007/978-3-319-15579-1_49.
• [30] Q. Zhang, Z. Su, “Context-sensitive data-dependence analysis via linear conjunctive language reachability”, Principles of Programming Languages (POPL 2017), pp. 344-358. URL http://dx.doi.org/10.1145/3009837.3009848.
• [31] R. Zier-Vogel, M. Domaratzki, “RNA pseudoknot prediction through stochastic conjunctive grammars”, The Nature of Computation: Logic, Algorithms, Applications (CiE 2013, Milan, Italy, 1-5 July 2013), Informal Proceedings, 2013 pp. 80-89.