Abstract
Kleene algebra with tests (KAT) is an equational system that extends Kleene algebra, the algebra of regular expressions, and that is specially suited to capture and verify properties of simple imperative programs. In this paper we study two constructions of automata from KAT expressions: the Glushkov automaton (\(\mathcal{A}_{\mathsf{pos}}\)), and a new construction based on the notion of prebase (equation automata, \(\mathcal{A}_{\mathsf{eq}}\)). Contrary to other automata constructions from KAT expressions, these two constructions enjoy the same descriptional complexity behaviour as their counterparts for regular expressions, both in the worst-case as well as in the average-case. In particular, our main result is to show that, asymptotically and on average the number of transitions of the \(\mathcal{A}_{{\mathsf{pos}}}\) is linear in the size of the KAT expression.
This work was funded by the European Regional Development Fund through the programme COMPETE and by the FCT under projects PEst-C/MAT/UI0144/2011, CANTE-PTDC/EIA-CCO/101904/2008, and FCOMP-01-0124-FEDER-020486.
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, R., Broda, S., Moreira, N.: Deciding KAT and Hoare logic with derivatives. In: Faella, M., Murano, A. (eds.) Proc. 3rd GANDALF. EPTCS, vol. 96, pp. 127–140 (2012)
Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On the average state complexity of partial derivative automata. International Journal of Foundations of Computer Science 22(7), 1593–1606 (2011)
Broda, S., Machiavelo, A., Moreira, N., Reis, R.: An introduction to descriptional complexity of regular languages through analytic combinatorics. Tech. Rep. DCC-2012-05, DCC - FC, Universidade do Porto (07 2012)
Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On the average size of Glushkov and partial derivative automata. International Journal of Foundations of Computer Science 23(5), 969–984 (2012)
Champarnaud, J.M., Ziadi, D.: From Mirkin’s prebases to Antimirov’s word partial derivatives. Fundam. Inform. 45(3), 195–205 (2001)
Champarnaud, J.M., Ziadi, D.: Canonical derivatives, partial derivatives and finite automaton constructions. Theoret. Comput. Sci. 289, 137–163 (2002)
Cohen, E., Kozen, D., Smith, F.: The complexity of Kleene algebra with tests. Tech. Rep. TR96-1598, Computer Science Department, Cornell University (07 1996)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. CUP (2008)
Glushkov, V.M.: The abstract theory of automata. Russian Math. Surveys 16, 1–53 (1961)
Kaplan, D.M.: Regular expressions and the equivalence of programs. J. Comput. Syst. Sci. 3(4), 361–386 (1969)
Kozen, D.: Kleene algebra with tests. Trans. on Prog. Lang. and Systems 19(3), 427–443 (1997)
Kozen, D.: Automata on guarded strings and applications. Matématica Contemporânea 24, 117–139 (2003)
Kozen, D.: On the coalgebraic theory of Kleene algebra with tests. Tech. Rep., Cornell University (05 2008), http://hdl.handle.net/1813/10173
Kozen, D., Smith, F.: Kleene algebra with tests: Completeness and decidability. In: van Dalen, D., Bezem, M. (eds.) CSL 1996. LNCS, vol. 1258, pp. 244–259. Springer, Heidelberg (1997)
Mirkin, B.G.: An algorithm for constructing a base in a language of regular expressions. Engineering Cybernetics 5, 51–57 (1966)
Nicaud, C.: On the average size of Glushkov’s automata. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 626–637. Springer, Heidelberg (2009)
Silva, A.: Kleene Coalgebra. Ph.D. thesis, Radboud Universiteit Nijmegen (2010)
Worthington, J.: Feasibly Reducing KAT Equations to KA Equations. ArXiv e-prints (01 2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Broda, S., Machiavelo, A., Moreira, N., Reis, R. (2013). On the Average Size of Glushkov and Equation Automata for KAT Expressions. In: Gąsieniec, L., Wolter, F. (eds) Fundamentals of Computation Theory. FCT 2013. Lecture Notes in Computer Science, vol 8070. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40164-0_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-40164-0_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40163-3
Online ISBN: 978-3-642-40164-0
eBook Packages: Computer ScienceComputer Science (R0)