Abstract
Multi-tilde-bar operators allow us to extend regular expressions. The associated extended expressions are compatible with the structure of Glushkov automata and they provide a more succinct representation than standard expressions. The aim of this paper is to examine the derivation of multi-tilde-bar expressions. Two types of computation are investigated: Brzozowski derivation and Antimirov derivation, as well as the construction of the associated automata.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Almeida, M., Moreira, N., Reis, R.: Antimirov and Mosses’s rewrite system revisited. Int. J. Found. Comput. Sci. 20(4), 669–684 (2009)
Antimirov, V.: Partial derivatives of regular expressions and finite automaton constructions. Theoret. Comput. Sci. 155, 291–319 (1996)
Antimirov, V.M., Mosses, P.D.: Rewriting extended regular expressions. Theor. Comput. Sci. 143(1), 51–72 (1995)
Berry, G., Sethi, R.: From regular expressions to deterministic automata. Theoret. Comput. Sci. 48(1), 117–126 (1986)
Brzozowski, J.A.: Derivatives of regular expressions. J. Assoc. Comput. Mach. 11(4), 481–494 (1964)
Brzozowski, J.A.: Quotient complexity of regular languages. Journal of Automata, Languages and Combinatorics 15(1/2), 71–89 (2010)
Brzozowski, J.A., Leiss, E.L.: On equations for regular languages, finite automata, and sequential networks. Theor. Comput. Sci. 10, 19–35 (1980)
Caron, P., Champarnaud, J.M., Mignot, L.: Erratum to “acyclic automata and small expressions using multi-tilde-bar operators”. [Theoret. Comput. Sci. 411(38-39), 3423–3435] (2010); Theor. Comput. Sci. 412(29), 3795–3796 (2011)
Caron, P., Champarnaud, J.M., Mignot, L.: Multi-bar and multi-tilde regular operators. Journal of Automata, Languages and Combinatorics 16(1), 11–26 (2011)
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)
Caron, P., Champarnaud, J.M., Mignot, L.: A general frame for the derivation of regular expressions (submitted, 2012)
Champarnaud, J.-M., Jeanne, H., Mignot, L.: Approximate Regular Expressions and Their Derivatives. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 179–191. Springer, Heidelberg (2012)
Champarnaud, J.M., Ouardi, F., Ziadi, D.: An efficient computation of the equation \(\mathbb{K}\)-automaton of a regular \(\mathbb{K}\)-expression. Fundam. Inform. 90(1-2), 1–16 (2009)
Champarnaud, J.M., Ziadi, D.: Canonical derivatives, partial derivatives, and finite automaton constructions. Theoret. Comput. Sci. 239(1), 137–163 (2002)
Conway, J.H.: Regular algebra and finite machines. Chapman and Hall (1971)
Frishert, M.: FIRE Works & FIRE Station: A finite automata and regular expression playground. Ph.D. thesis, Eindhoven University, Netherlands (2005)
Ginzburg, A.: A procedure for checking equality of regular expressions. J. ACM 14(2), 355–362 (1967)
Ilie, L., Yu, S.: Follow automata. Inf. Comput. 186(1), 140–162 (2003)
Kleene, S.: Representation of events in nerve nets and finite automata. Automata Studies Ann. Math. Studies 34, 3–41 (1956)
Krob, D.: Differentation of K-rational expressions. Internat. J. Algebra Comput. 2(1), 57–87 (1992)
Lombardy, S., Sakarovitch, J.: Derivatives of rational expressions with multiplicity. Theor. Comput. Sci. 332(1-3), 141–177 (2005)
Owens, S., Reppy, J.H., Turon, A.: Regular-expression derivatives re-examined. J. Funct. Program. 19(2), 173–190 (2009)
Sulzmann, M., Lu, K.: Partial derivative regular expression pattern matching (December 2007) (manuscript)
Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages. Word, Language, Grammar, vol. I, pp. 41–110. Springer, Berlin (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Caron, P., Champarnaud, JM., Mignot, L. (2012). Multi-Tilde-Bar Derivatives. In: Moreira, N., Reis, R. (eds) Implementation and Application of Automata. CIAA 2012. Lecture Notes in Computer Science, vol 7381. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31606-7_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-31606-7_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31605-0
Online ISBN: 978-3-642-31606-7
eBook Packages: Computer ScienceComputer Science (R0)