Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
The New Complexity Landscape Around Circuit Minimization Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

Cyclic Shift on Multi-component Grammars

verfasst von : Alexander Okhotin, Alexey Sorokin

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Multi-component grammars, known in the literature as “multiple context-free grammars” and “linear context-free rewriting systems”, describe the structure of a string by defining the properties of k-tuples of its substrings, in the same way as ordinary formal grammars (Chomsky’s “context-free”) define properties of substrings. It is shown that, for every fixed k, the family of languages described by k-component grammars is closed under the cyclic shift operation. On the other hand, the subfamily defined by well-nested k-component grammars is not closed under the cyclic shift, yet their cyclic shifts are always defined by well-nested \((k+1)\)-component grammars.

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 Context-Sensitive Fusion Grammars Are Universal
Nächstes Kapitel The Automatic Baire Property and an Effective Property of -Rational Functions
Fußnoten
1
Most of the proofs are omitted due to space restrictions.
 
Literatur
1.
2.
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Adison-Wesley, Reading (1979)MATH
3.
Jirásková, G., Okhotin, A.: State complexity of cyclic shift. RAIRO-Theoret. Inform. Appl. 42(2), 335–360 (2008)MathSciNetCrossRef
4.
5.
6.
Kanazawa, M.: Ogden’s lemma, multiple context-free grammars, and the control language hierarchy. Inf. Comput. (2019)
7.
Kanazawa, M., Kobele, G.M., Michaelis, J., Salvati, S., Yoshinaka, R.: The failure of the strong pumping lemma for multiple context-free languages. Theory Comput. Syst. 55(1), 250–278 (2014)MathSciNetCrossRef
8.
Kanazawa, M., Salvati, S.: Mix is not a tree-adjoining language. In: Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 666–674 (2012)
9.
Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad. Nauk 194(6), 1266–1268 (1970)MathSciNet
10.
Maslov, A.N.: Cyclic shift operation for languages. Problemy Peredachi Informatsii 9(4), 81–87 (1973)MathSciNet
11.
Okhotin, A.: Conjunctive and Boolean grammars: the true general case of the context-free grammars. Comput. Sci. Rev. 9, 27–59 (2013)CrossRef
12.
Oshiba, T.: Closure property of family of context-free languages under cyclic shift operation. Electron. Commun. Jpn 55(4), 119–122 (1972)MathSciNet
13.
Pollard, C.J.: Generalized phrase structure grammars, head grammars, and natural language. Ph.D. dissertation, Stanford University (1984)
14.
Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theoret. Comput. Sci. 88(2), 191–229 (1991)MathSciNetCrossRef
15.
16.
17.
18.
Vijay-Shanker, K., Weir, D.J., Joshi, A.K.: Characterizing structural descriptions produced by various grammatical formalisms. In: Proceedings of the 25th Annual Meeting on Association for Computational Linguistics, pp. 104–111. Association for Computational Linguistics (1987)
19.
Metadaten
Titel
Cyclic Shift on Multi-component Grammars
verfasst von
Alexander Okhotin
Alexey Sorokin
Copyright-Jahr
2020
Buch
Language and Automata Theory and Applications

Print ISBN: 978-3-030-40607-3

Electronic ISBN: 978-3-030-40608-0

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-030-40608-0_20