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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Decision Problems for Finite Automata over Infinite Algebraic Structures Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Derived-Term Automata of Multitape Rational Expressions

verfasst von : Akim Demaille

Erschienen in: Implementation and Application of Automata

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We introduce (weighted) rational expressions to denote series over Cartesian products of monoids. To this end, we propose the operator \(\mathbin {|}\) to build multitape expressions such as \((a^+\mathbin {|}x + b^+\mathbin {|}y)^*\). We define expansions, which generalize the concept of derivative of a rational expression, but relieved from the need of a free monoid. We propose an algorithm based on expansions to build multitape automata from multitape expressions.

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 Computing the Expected Edit Distance from a String to a PFA
Nächstes Kapitel Solving Parity Games Using an Automata-Based Algorithm
Fußnoten
2
Makarevskii and Stotskaya [11] define derivatives, but (i) in the case of expressions over tuples of letters, and (ii) only when in so-called “standard form”, for which he notes “no method of constructing [an] n-expression in standard form for a regular n-expression is known”.
 
Literatur
1.
Allauzen, C., Mohri, M.: A unified construction of the Glushkov, follow, and Antimirov automata. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 110–121. Springer, Heidelberg (2006)CrossRef
2.
Angrand, P.-Y., Lombardy, S., Sakarovitch, J.: On the number of broken derived terms of a rational expression. J. Autom. Lang. Comb. 15(1/2), 27–51 (2010)
3.
4.
5.
Caron, P., Champarnaud, J.-M., Mignot, L.: Partial derivatives of an extended regular expression. In: Dediu, A.-H., Inenaga, S., Martín-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 179–191. Springer, Heidelberg (2011)CrossRef
6.
Champarnaud, J.-M., Ouardi, F., Ziadi, D.: An efficient computation of the equation \({\mathbb{K}}\)-automaton of a regular \({\mathbb{K}}\)-expression. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 145–156. Springer, Heidelberg (2007)CrossRef
7.
8.
Demaille, A., Duret-Lutz, A., Lombardy, S., Sakarovitch, J.: Implementation concepts in Vaucanson 2. In: Konstantinidis, S. (ed.) CIAA 2013. LNCS, vol. 7982, pp. 122–133. Springer, Heidelberg (2013)CrossRef
9.
Kaplan, R.M., Kay, M.: Regular models of phonological rule systems. Comput. Linguist. 20(3), 331–378 (1994)
10.
11.
Makarevskii, A.Y., Stotskaya, E.D.: Representability in deterministic multi-tape automata. Cybern. Syst. Anal. 5(4), 390–399 (1969)CrossRef
12.
13.
Rutten, J.J.M.M.: Behavioural differential equations: a coinductive calculus of streams, automata, and power series. TCS 308(1–3), 1–53 (2003)MathSciNetCrossRefMATH
14.
Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (2009). Corrected English translation of Éléments de théorie des automates, Vuibert (2003)CrossRefMATH
15.
Thompson, K.: Programming techniques: regular expression search algorithm. Commun. ACM 11(6), 419–422 (1968)CrossRefMATH
Metadaten
Titel
Derived-Term Automata of Multitape Rational Expressions
verfasst von
Akim Demaille
Copyright-Jahr
2016
Buch
Implementation and Application of Automata

Print ISBN: 978-3-319-40945-0

Electronic ISBN: 978-3-319-40946-7

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-40946-7_5

Premium Partner

    Bildnachweise