nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

The Hardest Language for Conjunctive Grammars

verfasst von : Alexander Okhotin

Erschienen in: Computer Science – Theory and Applications

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

A famous theorem by Greibach (“The hardest context-free language”, SIAM J. Comp., 1973) states that there exists such a context-free language \(L_0\) that every context-free language over any alphabet is reducible to \(L_0\) by a homomorphic reduction—in other words, is representable as an inverse homomorphic image \(h^{-1}(L_0)\), for a suitable homomorphism h. This paper establishes similar characterizations for conjunctive grammars, that is, for grammars extended with a conjunction operator.

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 Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems

Nächstes Kapitel Low-Rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions

Aizikowitz, T., Kaminski, M.: LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol. 6651, pp. 345–358. Springer, Heidelberg (2011)CrossRef

Autebert, J.-M.: Non-principalité du cylindre des langages à compteur. Math. Syst. Theory 11(1), 157–167 (1977)MathSciNetCrossRefMATH

Barash, M., Okhotin, A.: An extension of context-free grammars with one-sided context specifications. Inf. Comput. 237, 268–293 (2014)MathSciNetCrossRefMATH

Barash, M., Okhotin, A.: Two-sided context specifications in formal grammars. Theoret. Comput. Sci. 591, 134–153 (2015)MathSciNetCrossRefMATH

Boasson, L., Nivat, M.: Le cylindre des langages linéaires. Math. Syst. Theory 11, 147–155 (1977)MathSciNetCrossRefMATH

Čulík II, K., Maurer, H.A.: On simple representations of language families. RAIRO Informatique Théorique et Appl. 13(3), 241–250 (1979)MathSciNetMATH

Greibach, S.A.: A new normal-form theorem for context-free phrase structure grammars. J. ACM 12, 42–52 (1965)MathSciNetCrossRefMATH

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

Greibach, S.A.: Jump PDA’s and hierarchies of deterministic context-free languages. SIAM J. Comput. 3(2), 111–127 (1974)MathSciNetCrossRefMATH

10.

Kountouriotis, V., Nomikos, C., Rondogiannis, P.: Well-founded semantics for Boolean grammars. Inf. Comput. 207(9), 945–967 (2009)MathSciNetCrossRefMATH

11.

Lehtinen, T., Okhotin, A.: Boolean grammars and GSM mappings. Int. J. Found. Comput. Sci. 21(5), 799–815 (2010)MathSciNetCrossRefMATH

12.

Okhotin, A.: Conjunctive grammars. J. Automata Lang. Comb. 6(4), 519–535 (2001)MathSciNetMATH

13.

Okhotin, A.: Conjunctive grammars and systems of language equations. Program. Comput. Sci. 28(5), 243–249 (2002)MathSciNetCrossRefMATH

14.

Okhotin, A.: Boolean grammars. Inf. Comput. 194(1), 19–48 (2004)MathSciNetCrossRefMATH

15.

Okhotin, A.: The dual of concatenation. Theoret. Comput. Sci. 345(2–3), 425–447 (2005)MathSciNetCrossRefMATH

16.

Okhotin, A.: Conjunctive and Boolean grammars: the true general case of the context-free grammars. Comput. Sci. Rev. 9, 27–59 (2013)CrossRefMATH

17.

Okhotin, A.: Parsing by matrix multiplication generalized to Boolean grammars. Theoret. Comput. Sci. 516, 101–120 (2014)MathSciNetCrossRefMATH

18.

Okhotin, A., Reitwießner, C.: Conjunctive grammars with restricted disjunction. Theoret. Comput. Sci. 411(26–28), 2559–2571 (2010)MathSciNetCrossRefMATH

19.

Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theoret. Comput. Sci. 88(2), 191–229 (1991)MathSciNetCrossRefMATH

20.

Vijay-Shanker, K., Weir, D.J., Joshi, A.K.: Characterizing structural descriptions produced by various grammatical formalisms. In: 25th Annual Meeting of the Association for Computational Linguistics (ACL 1987), pp. 104–111 (1987)

Titel: The Hardest Language for Conjunctive Grammars
verfasst von: Alexander Okhotin
Verlag: Springer International Publishing
Buch: Computer Science – Theory and Applications
Print ISBN: 978-3-319-34170-5

Electronic ISBN: 978-3-319-34171-2

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-34171-2_24

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"