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
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Verification of Concurrent Programs on Weak Memory Models Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Derived-Term Automata for Extended Weighted Rational Expressions

verfasst von : Akim Demaille

Erschienen in: Theoretical Aspects of Computing – ICTAC 2016

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We present an algorithm to build an automaton from a rational expression. This approach introduces support for extended weighted expressions. Inspired by derived-term based algorithms, its core relies on a different construct, rational expansions. We introduce an inductive algorithm to compute the expansion of an expression from which the automaton follows. This algorithm is independent of the size of the alphabet, and actually even supports infinite alphabets. It can easily be accommodated to generate deterministic (weighted) automata. These constructs are implemented in Vcsn, a free-software platform dedicated to weighted automata and rational 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 ProofScript: Proof Scripting for the Masses
Nächstes Kapitel Weighted Register Automata and Weighted Logic on Data Words
Fußnoten
2
The induction is on the length of the word u in https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-46750-4_20/420064_1_En_20_IEq192_HTML.gif , which is defined for all q and all words of the given length simultaneously.
 
3
Vcsn 2.2 as of 2016-05-16, compiled with Clang 3.6 with options -O3 -DNDEBUG, and run on a Mac OS X 10.11.4, Intel Core i7 2.9GHz, 8GB of RAM. Best run out of five.
 
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). doi:10.​1007/​11821069_​10 CrossRef
2.
Angrand, P.-Y., Lombardy, S., Sakarovitch, J.: On the number of broken derived terms of a rational expression. J. Automata 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). doi:10.​1007/​978-3-642-21254-3_​13 CrossRef
6.
Champarnaud, J.-M., Ziadi, D.: From Mirkin’s prebases to Antimirov’s word partial derivatives. Fundam. Inf. 45(3), 195–205 (2001)MathSciNetMATH
7.
Champarnaud, J.-M., Ziadi, D.: Canonical derivatives, partial derivatives and finite automaton constructions. TCS 289(1), 137–163 (2002)MathSciNetCrossRefMATH
8.
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). doi:10.​1007/​978-3-540-73208-2_​16 CrossRef
9.
10.
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). doi:10.​1007/​978-3-642-39274-0_​12 CrossRef
11.
Fischer, S., Huch, F., Wilke, T.: A play on regular expressions: functional pearl. In: Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, ICFP 2010, pp. 357–368. ACM (2010)
12.
13.
Kaplan, R.M., Kay, M.: Regular models of phonological rule systems. Comput. Linguist. 20(3), 331–378 (1994)
14.
15.
McNaughton, R., Yamada, H.: Regular expressions and state graphs for automata. IEEE Trans. Electron. Comput. 9, 39–47 (1960)CrossRefMATH
16.
Mirkin, B.G.: An algorithm for constructing a base in a language of regular expressions. Eng. Cybern. 5, 110–116 (1966)
17.
18.
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
19.
Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press (2009). Corrected English translation of Éléments de théorie des automates, Vuibert, 2003
Metadaten
Titel
Derived-Term Automata for Extended Weighted Rational Expressions
verfasst von
Akim Demaille
Copyright-Jahr
2016
Buch
Theoretical Aspects of Computing – ICTAC 2016

Print ISBN: 978-3-319-46749-8

Electronic ISBN: 978-3-319-46750-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-46750-4_20

Premium Partner

    Bildnachweise