nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

On the Expressive Power of GF(2)-Grammars

verfasst von : Vladislav Makarov, Alexander Okhotin

Erschienen in: SOFSEM 2019: Theory and Practice of Computer Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

GF(2)-grammars, recently introduced by Bakinova et al. (“Formal languages over GF(2)”, LATA 2018), are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: \(K \odot L\) is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L. This paper establishes several results on the family of languages defined by these grammars. Over the unary alphabet, GF(2)-grammars define exactly the 2-automatic sets. No language of the form \(\{a^n b^{f(n)} \,\mid \, n \geqslant 1\}\), with uniformly superlinear f, can be described by any GF(2)-grammar. The family is not closed under union, intersection, classical concatenation and Kleene star, non-erasing homomorphisms. On the other hand, this family is closed under injective nondeterministic finite transductions, and contains a hardest language under reductions by homomorphisms.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Towards Automatic Comparison of Cloud Service Security Certifications

Nächstes Kapitel An Efficient Algorithm for Combining Verification and Validation Methods

Allouche, J.-P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003)CrossRef

Bakinova, E., Basharin, A., Batmanov, I., Lyubort, K., Okhotin, A., Sazhneva, E.: Formal languages over GF(2). In: Klein, S.T., Martín-Vide, C., Shapira, D. (eds.) LATA 2018. LNCS, vol. 10792, pp. 68–79. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-77313-1_5CrossRef

Barash, M., Okhotin, A.: An extension of context-free grammars with one-sided context specifications. Inf. Comput. 237, 268–293 (2014). https://doi.org/10.1016/j.ic.2014.03.003MathSciNetCrossRefMATH

Buchholz, T., Kutrib, M.: On time computability of functions in one-way cellular automata. Acta Informatica 35(4), 329–352 (1998). https://doi.org/10.1007/s002360050123MathSciNetCrossRefMATH

Christol, G.: Ensembles presque periodiques \(k\)-reconnaissables. Theor. Comput. Sci. 9, 141–145 (1979). https://doi.org/10.1016/0304-3975(79)90011-2MathSciNetCrossRefMATH

Eilenberg, S.: Automata, Languages and Machines, vol. 1. Academic Press, Cambridge (1974)MATH

Forejt, V., Jančar, P., Kiefer, S., Worrell, J.: Language equivalence of probabilistic pushdown automata. Inf. Comput. 237, 1–11 (2014). https://doi.org/10.1016/j.ic.2014.04.003MathSciNetCrossRefMATH

Ginsburg, S., Rice, H.G.: Two families of languages related to ALGOL. J. ACM 9, 350–371 (1962). https://doi.org/10.1145/321127.321132MathSciNetCrossRefMATH

Ginsburg, S., Spanier, E.H.: Quotients of context-free languages. J. ACM 10(4), 487–492 (1963). https://doi.org/10.1145/321186.321191MathSciNetCrossRefMATH

10.

Greibach, S.A.: The hardest context-free language. SIAM J. Comput. 2(4), 304–310 (1973). https://doi.org/10.1137/0202025MathSciNetCrossRefMATH

11.

Ibarra, O.H., Kim, S.M.: Characterizations and computational complexity of systolic trellis automata. Theor. Comput. Sci. 29, 123–153 (1984). https://doi.org/10.1016/0304-3975(84)90015-XMathSciNetCrossRefMATH

12.

Jeż, A.: Conjunctive grammars can generate non-regular unary languages. Int. J. Found. Comput. Sci. 19(3), 597–615 (2008). https://doi.org/10.1142/S012905410800584XCrossRefMATH

13.

Knuth, D.E.: Context-free multilanguages. In: Theoretical Studies in Computer Science, pp. 1–13. Academic Press, Cambridge (1992)

14.

Okhotin, A.: On the equivalence of linear conjunctive grammars to trellis automata. RAIRO Informatique Théorique et Applications 38(1), 69–88 (2004). https://doi.org/10.1051/ita:2004004MathSciNetCrossRefMATH

15.

Okhotin, A.: Conjunctive and Boolean grammars: the true general case of the context-free grammars. Comput. Sci. Rev. 9, 27–59 (2013). https://doi.org/10.1016/j.cosrev.2013.06.001CrossRefMATH

16.

Okhotin, A.: Input-driven languages are linear conjunctive. Theor. Comput. Sci. 618, 52–71 (2016). https://doi.org/10.1016/j.tcs.2016.01.007MathSciNetCrossRefMATH

17.

Okhotin, A.: Underlying principles and recurring ideas of formal grammars. In: Klein, S.T., Martín-Vide, C., Shapira, D. (eds.) LATA 2018. LNCS, vol. 10792, pp. 36–59. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-77313-1_3CrossRefMATH

18.

Petre, I., Salomaa, A.: Algebraic systems and pushdown automata. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata, pp. 257–289. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01492-5_7CrossRef

19.

Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theor. Comput. Sci. 88(2), 191–229 (1991). https://doi.org/10.1016/0304-3975(91)90374-BMathSciNetCrossRefMATH

20.

Terrier, V.: On real-time one-way cellular array. Theor. Comput. Sci. 141(1–2), 331–335 (1995). https://doi.org/10.1016/0304-3975(94)00212-2MathSciNetCrossRefMATH

Titel: On the Expressive Power of GF(2)-Grammars
verfasst von: Vladislav Makarov
Alexander Okhotin
Verlag: Springer International Publishing
Buch: SOFSEM 2019: Theory and Practice of Computer Science
Print ISBN: 978-3-030-10800-7

Electronic ISBN: 978-3-030-10801-4

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-10801-4_25

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"