Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Verification of Concurrent Programs on Weak Memory Models Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Derived-Term Automata for Extended Weighted Rational Expressions

Author : Akim Demaille

Published in: Theoretical Aspects of Computing – ICTAC 2016

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter ProofScript: Proof Scripting for the Masses
next chapter Weighted Register Automata and Weighted Logic on Data Words
Footnotes
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.
 
Literature
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
Metadata
Title
Derived-Term Automata for Extended Weighted Rational Expressions
Author
Akim Demaille
Copyright Year
2016
Book
Theoretical Aspects of Computing – ICTAC 2016

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

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

Copyright Year: 2016

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

Premium Partner

    Image Credits