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 5/2014

01.08.2014 | Original Article

Controlled finite automata

verfasst von: Alexander Meduna, Petr Zemek

Erschienen in: Acta Informatica | Ausgabe 5/2014

Einloggen

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

search-config
loading …

Abstract

This paper discusses finite automata regulated by control languages over their states and transition rules. It proves that under both regulations, regular-controlled finite automata and context-free-controlled finite automata characterize the family of regular languages and the family of context-free languages, respectively. It also establishes conditions under which any state-controlled finite automaton can be turned into an equivalent transition-controlled finite automaton and vice versa. The paper also demonstrates a close relation between these automata and programmed grammars. Indeed, it proves that finite automata controlled by languages generated by propagating programmed grammars with appearance checking are computationally complete. In fact, it demonstrates that this computational completeness holds even in terms of these automata with a reduced number of states.
Vorheriger Artikel Forward and backward application of symbolic tree transducers

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
Literatur
1.
Csuhaj-Varjú, E., Masopust, T., Vaszil, G.: Blackhole state-controlled regulated pushdown automata. In: Second Workshop on Non-Classical Models for Automata and Applications (NCMA 2010) pp. 45–56 (2010)
2.
Csuhaj-Varjú, E., Masopust, T., Vaszil, G.: Blackhole pushdown automata. Fundam. Inform. 112(2–3), 137–156 (2011)MATH
3.
Dassow, J., Păun, G.: Regulated Rewriting in Formal Language Theory. Springer, Berlin (1989)CrossRef
4.
Hopcroft, J., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley, Boston (2000)
5.
Jantzen, M., Kudlek, M., Zetzsche, G.: Finite automata controlled by Petri nets. In: Proceedings of the 14th Workshop; Algorithmen und Werkzeuge für Petrinetze. Technical Report Nr. 25/2007, pp. 57–62. Universität Koblenz-Landau (2007)
6.
Kolář, D., Meduna, A.: Regulated pushdown automata. Acta Cybern. 2000(4), 653–664 (2000)
7.
Kolář, D., Meduna, A.: One-turn regulated pushdown automata and their reduction. Fundam. Inform. 2001(21), 1001–1007 (2001)
8.
Kolář, D., Meduna, A.: Regulated automata: from theory towards applications. In: Proceeding of 8th International Conference on Information Systems Implementation and Modelling (ISIM’05) pp. 33–48 (2005)
9.
Meduna, A.: Automata and Languages: Theory and Applications. Springer, London (2000)CrossRef
10.
Meduna, A., Masopust, T.: Self-regulating finite automata. Acta Cybern. 18(1), 135–153 (2007)MATHMathSciNet
11.
Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, Vol. 2: Linear Modeling: Background and Application. Springer, New York (1997)
12.
Rychnovský, L.: Regulated pushdown automata revisited. In: Proceedings of the 15th Conference STUDENT EEICT 2009, pp. 440–444. Faculty of Information Technology BUT, Brno, CZ (2009)
13.
Wood, D.: Theory of Computation: A Primer. Addison-Wesley, Boston (1987)
Metadaten
Titel
Controlled finite automata
verfasst von
Alexander Meduna
Petr Zemek
Publikationsdatum
01.08.2014
Verlag
Springer Berlin Heidelberg
Erschienen in
Acta Informatica / Ausgabe 5/2014
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-014-0199-5