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
Acta Informatica
Erschienen in: Acta Informatica 3/2013

01.05.2013 | Original Article

Conjunctive grammars and alternating pushdown automata

verfasst von: Tamar Aizikowitz, Michael Kaminski

Erschienen in: Acta Informatica | Ausgabe 3/2013

Einloggen

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

search-config
loading …

Abstract

In this paper we introduce a variant of alternating pushdown automata, synchronized alternating pushdown automata, which accept the same class of languages as those generated by conjunctive grammars.
Vorheriger Artikel Avoiding cross-bifix-free binary words
Nächster Artikel Verifying a simplification of mutual exclusion by Lycklama–Hadzilacos

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 "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

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
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Semi-extended regular expressions contain an explicit operator for intersection.
 
2
We call two models equivalent if they recognize/generate the same class of languages.
 
3
One-turn PDA are a sub-family of pushdown automata, where in each computation the stack height switches only once from non-decreasing to non-increasing. That is, once a transition replaces the top symbol of the stack with \(\epsilon \), all subsequent transitions may write at most one character.
 
4
The languages accepted, respectively, derived, by these two models properly include the boolean closure of deterministic context-free languages.
 
5
This type of formalization is standard in the field of formal verification, see [13], say.
 
6
This is similar to the concept of a transition from a universal state in the standard formalization of alternating automata, as all branches must accept.
 
7
Alternatively, one can extend the definition of \(A\) with a set of accepting states \(F \subseteq Q\), and define collapsing and acceptance by accepting states, similarly to the classical definition. It can readily be seen that such an extension results in an equivalent model of computation.
 
8
We omit the state components of both \(A_G\) and \(\delta \).
 
9
If \(X_j \in \Sigma \), then \(w_j = X_j\).
 
Literatur
Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling, Volume I Parsing. Prentice-Hall, Englewood Cliffs (1972)
Aizikowitz, T., Kaminski, M.: Conjunctive grammars and alternating pushdown automata. In: Hodges, W., de Queiroz, R. (Eds.) The 15th Workshop on Logic, Language, Information and Computation—WoLLIC’2008, Volume 5110 of Lecture Notes in Artificial Intelligence, pp. 30–41. Springer, Berlin/Heidelberg (2008)
Aizikowitz, T., Kaminski, M.: Linear conjunctive grammars and one-turn synchronized alternating pushdown automata. In: de Groote, P., Egg, M., Kallmeyer, L. (Eds.) Formal Grammar, 14th International Conference—FG 2009, Volume 5591 of Lecture Notes in Artificial Intelligence, pp. 1–16. Springer, Berlin/Heidelberg (2011)
Aizikowitz, T., Kaminski, M.: \(LR(0)\) conjunctive grammars and deterministic synchronized alternating pushdown automata. In: Kulikov, A.S., Vereshchagin, N.K. (Eds.) The 6th International Computer Science Symposium in Russia—CSR 2011, Volume 6651 of Lecture Notes in Computer Science, pp. 345–358. Springer, Berlin/Heidelberg (2011)
Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, pp. 202–211. ACM (2004)
Culik, K., II, Gruska, J., Salomaa, A.: Systolic trellis automata, I and II. Int. J. Comput. Math. 15 and 16, 195–212 and 3–22 (1984)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)MATH
Jez, A., Okhotin, A.: Conjunctive grammars over a unary alphabet: undecidability and unbounded growth. Theory Comput. Syst. 46, 27–58 (2010)MathSciNetMATHCrossRef
Kupferman, O., Vardi, M.Y.: Weak alternating automata are not that weak. ACM Trans. Comput. Logic 2, 408–429 (2001)
Kupferman, O., Zuhovitzky, Sh: An improved algorithm for the membership problem for extended regular expressions. In: Diks, K., Rytter, W. (Eds.) Mathematical Foundations of Computer Science, Volume 2420 of Lecture Notes in Computer Science, pp. 446–458. Springer, Berlin/Heidelberg (2002)
Ladner, R.E., Lipton, R.J., Stockmeyer, L.J.: Alternating pushdown and stack automata. SIAM J. Comput. 13(1), 135–155 (1984)MathSciNetMATHCrossRef
Masaru, T.: Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. Kluwer, Norwell (1985)
Okhotin, A.: Conjunctive Langauges are Closed Under Inverse Homomorphism. Technical Report 2003/468, School of Computing, Queens University (2003)
Okhotin, A.: Efficient automaton-based recognition for linear conjunctive languages. Int. J. Found. Comput. Sci. 14(6), 1103–1116 (2003)MathSciNetMATHCrossRef
Okhotin, A.: A recognition and parsing algorithm for arbitrary conjunctive grammars. Theor. Comput. Sci. 302, 81–124 (2003)MathSciNetCrossRef
Okhotin, A.: On the equivalence of linear conjunctive grammars and trellis automata. RAIRO Theor. Inform. Appl. 38(1), 69–88 (2004)MathSciNetMATHCrossRef
Okhotin, A., Reitwießner, C.: Conjunctive grammars with restricted disjunction. Theor. Comput. Sci. 411, 2559–2571 (2010)MATHCrossRef
Yamamoto, H.: An automata-based recognition algorithm for semi-extended regular expressions. In: Nielsen, M., Rovan, B. (Eds.) Mathematical Foundations of Computer Science—MFCS 2000, 25th International Symposium, Volume 1893 of Lecture Notes in Computer Science, pp. 699–708. Springer, Berlin/Heidelberg (2000)
Metadaten
Titel
Conjunctive grammars and alternating pushdown automata
verfasst von
Tamar Aizikowitz
Michael Kaminski
Publikationsdatum
01.05.2013
Verlag
Springer-Verlag
Erschienen in
Acta Informatica / Ausgabe 3/2013
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-013-0177-3