Published in Volume XXVII, Issue 2, 2017, pages 137-176, doi: 10.7561/SACS.2017.2.137

Authors: A. Demaille


Rational expressions are powerful tools to define automata, but often restricted to single-tape automata. Our goal is to unleash their expressive power for transducers, and more generally, any multitape automaton; for instance (a+|x+b+|y)*. We generalize the construction of the derived-term automaton by using expansions. This  approach generates small automata, and even allows us to support a composition operator.

Full Text (PDF)


[1] C. Allauzen and M. Mohri. A unified construction of the Glushkov, follow, and Antimirov automata. In R. Kalovic and P. Urzyczyn, editors, Mathematical Foundations of Computer Science, volume 4162 of Lecture Notes in Computer Science, pages 110–121. Springer Berlin Heidelberg, 2006. doi:10.1007/11821069_10.

[2] P.-Y. Angrand, S. Lombardy, and J. Sakarovitch. On the number of broken derived terms of a rational expression. Journal of Automata, Languages and Combinatorics, 15(1/2):27–51, 2010.

[3] V. Antimirov. Partial derivatives of regular expressions and finite automaton constructions. Theoretical Computer Science, 155(2):291–319, 1996. doi: 10.1016/0304-3975(95)00182-4.

[4] J.A. Brzozowski. Derivatives of regular expressions. Journal of the ACM, 11(4):481–494, 1964. doi:10.1145/321239.321249.

[5] P. Caron, J.-M. Champarnaud, and Ludovic Mignot. Partial derivatives of an extended regular expression. In A.-H. Dediu, S. Inenaga, and C. Martín-Vide, editors, Language and Automata Theory and Applications, volume 6638 of Lecture Notes in Computer Science, pages 179–191. Springer Berlin Heidelberg, 2011. doi:10.1007/978-3-642-21254-3_13.

[6] P. Caron and M. Flouret. Glushkov construction for multiplicities. In S. Yu and A. Păun, editors, Implementation and Application of Automata: 5th International Conference, CIAA 2000 London, Ontario, Canada, July 24–25, 2000 Revised Papers, pages 67–79, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. doi:10.1007/3-540-44674-5_5.

[7] J.-M. Champarnaud, F. Ouardi, and D. Ziadi. An efficient computation of the equation K-automaton of a regular K-expression. In T. Harju, J. Karhum¨aki, and A. Lepist¨o, editors, Developments in Language Theory, volume 4588 of Lecture Notes in Computer Science, pages 145–156. Springer Berlin Heidelberg, 2007. doi:10.1007/978-3-540-73208-2_16.

[8] A. Demaille. Derived-term automata for extended weighted rational expressions. In A. Sampaio and F. Wang, editors, Theoretical Aspects of Computing – ICTAC 2016 – 13th International Colloquium, Taipei, Taiwan, ROC, October 24-31, 2016, Proceedings, volume 9965 of Lecture Notes in Computer Science, pages 351–369, 2016. doi:10.1007/978-3-319-46750-4_20.

[9[ A. Demaille. Derived-term automata of multitape rational expressions. In Y.-S. Han and K. Salomaa, editors, Proceedings of Implementation and Application of Automata, 21st International Conference (CIAA’16), volume 9705 of Lecture Notes in Computer Science, pages 51–63, Seoul, South Korea, July 2016. Springer. doi:10.1007/978-3-319-40946-7_5.

[10] A. Demaille, A. Duret-Lutz, S. Lombardy, and J. Sakarovitch. Implementation concepts in Vaucanson 2. In S. Konstantinidis, editor, Proceedings of Implementation and Application of Automata, 18th International Conference (CIAA’13), volume 7982 of Lecture Notes in Computer Science, pages 122–133, Halifax, NS, Canada, July 2013. Springer. doi:10.1007/978-3-642-39274-0_12.

[11] Z. Ésik and W. Kuich. Equational axioms for a theory of automata. In C. Martín-Vide, V. Mitrana, and G. Păun, editors, Formal Languages and Applications, pages 183–196. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. doi:10.1007/978-3-540-39886-8_10.

[12] V. M. Glushkov. The abstract theory of automata. Russian Math. Surveys, 16:1–53, 1961. doi:10.1070/RM1961v016n05ABEH004112.

[13] Ronald M. Kaplan and Martin Kay. Regular models of phonological rule systems. Computational Linguistics – Special issue on computational phonology, 20(3):331–378, September 1994.

[14] S. C. Kleene. Representation of events in nerve nets and finite automata. In Claude Shannon and John McCarthy, editors, Automata Studies, pages 3–41. Princeton University Press, Princeton, NJ, 1956.

[15] Dexter C. Kozen. Automata and Computability. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1st edition, 1997. doi:10.1007/978-1-4612-1844-9.

[16] S. Lombardy and J. Sakarovitch. Derivatives of rational expressions with multiplicity. Theoretical Computer Science, 332(1-3):141–177, 2005. doi: 10.1016/j.tcs.2004.10.016.

[17] S. Lombardy and J. Sakarovitch. The validity of weighted automata. Int. J. of Algebra and Computation, 23(4):863–914, 2013. doi:10.1142/S0218196713400146.

[18] A. Ya. Makarevskii and E. D. Stotskaya. Representability in deterministic multi-tape automata. Cybernetics and System Analysis, 5(4):390–399, 1969. doi:10.1007/BF01073050.

[19] R. McNaughton and H. Yamada. Regular expressions and state graphs for automata. IEEE Transactions on Electronic Computers, 9:39–47, 1960. doi: 10.1109/TEC.1960.5221603.

[20] M. Mohri. Edit-distance of weighted automata: General definitions and algorithms. International Journal of Foundations of Computer Science, 14(6):957– 982, 2003. doi:10.1142/S0129054103002114.

[21] T. Ng. Prefix distance between regular languages. In Y.S. Han and K. Salomaa, editors, Implementation and Application of Automata – 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings, pages 224–235, 2016. doi:10.1007/978-3-319-40946-7_19.

[22] S. Owens, J. Reppy, and A. Turon. Regular-expression derivatives re-examined. Journal of Functional Programming, 19(2):173–190, March 2009. doi:10.1017/S0956796808007090.

[23] J.J.M.M. Rutten. Behavioural differential equations: a coinductive calculus of streams, automata, and power series. Theoretical Computer Science, 308(1-3):1– 53, 2003. doi:10.1016/S0304-3975(02)00895-2.

[24] J. Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Corrected English translation of E´l´ements de th´eorie des automates, Vuibert, 2003. doi:10.1017/CBO9781139195218.

[25] K. Thompson. Programming techniques: Regular expression search algorithm. Communications of the ACM, 11(6):419–422, 1968. doi:10.1145/363347.363387.


  title={Derived-Term Automata of Multitape Expressions with Composition},
  author={A. Demaille},
  journal={Scientific Annals of Computer Science},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  publisher={``A.I. Cuza'' University Press}