Published in Volume XXII, Issue 2, 2012, pages 367-394, doi: 10.7561/SACS.2012.2.367

Authors: A. Silva

Abstract

Kleene algebra with tests (KAT) is an equational system that combines
Kleene and Boolean algebras. One can model basic programming constructs
and assertions in KAT, which allowed for its application in compiler
optimization, program transformation and dataflow analysis. To provide semantics for KAT expressions, Kozen first introduced emph{automata on guarded strings}, showing that the regular sets of guarded strings plays the same role in KAT as regular languages play in Kleene algebra. Recently, Kozen described an elegant algorithm, based on “derivatives”, to construct a deterministic automaton that accepts the guarded strings denoted by a KAT expression. This algorithm generalizes Brzozowski’s algorithm for regular
expressions and inherits its inefficiency arising from the explicit computation of derivatives.
In the context of classical regular expressions, many efficient algorithms to compile expressions to automata have been proposed. One of those algorithms was devised by Berry and Sethi in the 80’s (we shall refer to it as Berry-Sethi construction/algorithm, but in the literature it is also referred to as position or Glushkov automata algorithm).
In this paper, we show how the Berry-Sethi algorithm can be used to compile a $KAT$ expression to an automaton on guarded strings. Moreover, we propose a new automata model for KAT expressions and adapt the construction of Berry and Sethi to this new model.

Full Text (PDF)

References

[1] Allegra Angus and Dexter Kozen. Kleene algebra with tests and pro-
gram schematology. Technical Report TR2001-1844, Computing and
Information Science, Cornell University, July 2001.

[2] Valentin M. Antimirov. Partial derivatives of regular expressions and
nite automaton constructions. Theor. Comput. Sci., 155(2):291-319,
1996. http://dx.doi.org/10.1016/0304-3975(95)00182-4 .

[3] Falk Bartels. On generalized coinduction and probabilistic speci cation
formats. PhD thesis, Vrije Universiteit Amsterdam, 2004. PhD thesis.

[4] Gerard Berry and Ravi Sethi. From regular expressions to deterministic
automata. Theor. Comput. Sci., 48(3):117-126, 1986. http://dx.doi.org/10.1016/0304-3975(86)90088-5 .

[5] Janusz A. Brzozowski. Derivatives of regular expressions. Journal of
the ACM, 11(4):481-494, 1964. http://dx.doi.org/10.1145/321239.321249 .

[6] Jean-Marc Champarnaud, Florent Nicart, and Djelloul Ziadi. From the
ZPC structure of a regular expression to its follow automaton. IJAC,
16(1):17-34, 2006. http://dx.doi.org/10.1142/S0218196706002895 .

[7] Jean-Marc Champarnaud and Djelloul Ziadi. Canonical derivatives,
partial derivatives and nite automaton constructions. Theor. Comput.
Sci., 289(1):137-163, 2002. http://dx.doi.org/10.1016/S0304-3975(01)00267-5 .

[8] V.M. Glushkov. The abstract theory of automata. Russian Math.
Surveys, 16:1-53, 1961. http://dx.doi.org/10.1070/RM1961v016n05ABEH004112 .

[9] Bart Jacobs. A bialgebraic review of deterministic automata, regular
expressions and languages. In Kokichi Futatsugi, Jean-Pierre Jouannaud,
and Jose Meseguer, editors, Essays Dedicated to Joseph A. Goguen,
volume 4060 of Lecture Notes in Computer Science, pages 375-404.
Springer, 2006. http://dx.doi.org/10.1007/11780274_20 .

[10] Donald M. Kaplan. Regular expressions and the equivalence of pro-
grams. J. Comput. Syst. Sci., 3(4):361-386, 1969. http://dx.doi.org/10.1016/S0022-0000(69)80027-9 .

[11] Dexter Kozen. Automata and Computability. Springer-Verlag New York,
Inc., Secaucus, NJ, USA, 1997.

[12] Dexter Kozen. Automata on guarded strings and applications.
Matematica Contempor^anea, 24:117-139, 2003.

[13] Dexter Kozen. Nonlocal
ow of control and Kleene algebra with tests.
In Proceedings of the Twenty-Third Annual IEEE Symposium on Logic
in Computer Science, LICS 2008, 24-27 June 2008, Pittsburgh, PA,
USA, pages 105-117. IEEE Computer Society, 2008. http://dx.doi.org/10.1109/LICS.2008.32 .

[14] Dexter Kozen. On the coalgebraic theory of Kleene algebra with tests.
Technical Report http://hdl.handle.net/1813/10173 , Computing and
Information Science, Cornell University, March 2008.

[15] Dexter Kozen and Maria-Christina Patron. Certi cation of com-
piler optimizations using Kleene algebra with tests. In John W.
Lloyd, Veronica Dahl, Ulrich Furbach, Manfred Kerber, Kung-Kiu
Lau, Catuscia Palamidessi, Lus Moniz Pereira, Yehoshua Sagiv,
and Peter J. Stuckey, editors, Computational Logic, volume 1861 of
Lecture Notes in Computer Science, pages 568-582. Springer, 2000.
http://dx.doi.org/10.1007/3-540-44957-4_38 .

[16] Robert McNaughton and H. Yamada. Regular expressions and state
graphs for automata. IRE Transactions on Electronic Computers,
9(1):39-47, 1960. http://dx.doi.org/10.1109/TEC.1960.5221603 .

[17] Michael O. Rabin and D. Scott. Finite automata and their decision
problems. IBM Journal of Research and Development, 3:114-125, 1959.
http://dx.doi.org/10.1147/rd.32.0114 .

[18] Jan J. M. M. Rutten. Automata and coinduction (an exercise in coalge-
bra). In Davide Sangiorgi and Robert de Simone, editors, CONCUR,
volume 1466 of Lecture Notes in Computer Science, pages 194-218.
Springer, 1998. http://dx.doi.org/10.1007/BFb0055624 .

[19] Jan J. M. M. Rutten. Universal coalgebra: a theory of systems.
Theor. Comput. Sci., 249(1):3-80, 2000. http://dx.doi.org/10.1016/S0304-3975(00)00056-6 .

[20] Alexandra Silva. Kleene coalgebra. PhD thesis, Radboud University
Nijmegen, 2010.

[21] Ken Thompson. Programming techniques: Regular expression search
algorithm. Commun. ACM, 11(6):419-422, 1968. http://dx.doi.org/10.1145/363347.363387 .

Bibtex

@article{sacscuza:silva2012pafkawt,
  title={Position Automata for Kleene Algebra with Tests},
  author={A. Silva},
  journal={Scientific Annals of Computer Science},
  volume={22},
  number={2},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2012},
  pages={367--394},
  doi={10.7561/SACS.2012.2.367},
  publisher={``A.I. Cuza'' University Press}
}