×

zbMATH — the first resource for mathematics

Left-handed completeness. (English) Zbl 1436.68202
Summary: We give a new proof of the completeness of the left-handed star rule of Kleene algebra. The proof is significantly shorter than previous proofs and exposes the rich interaction of algebra and coalgebra in the theory of Kleene algebra.
MSC:
68Q70 Algebraic theory of languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Boffa, Maurice, Une condition impliquant toutes les identités rationnelles, Inform. Théor. Appl., 29, 6, 515-518 (1995) · Zbl 0881.68071
[2] Brzozowski, Janusz A., Canonical regular expressions and minimal state graphs for definite events, (Mathematical Theory of Automata. Mathematical Theory of Automata, MRI Symposia Series, vol. 12 (1962), Polytechnic Press, Polytechnic Institute of Brooklyn: Polytechnic Press, Polytechnic Institute of Brooklyn N.Y.), 529-561
[3] Conway, John Horton, Regular Algebra and Finite Machines (1971), Chapman and Hall: Chapman and Hall London, Dover edition, 2012
[4] Das, Anupam; Doumane, Amina; Pous, Damien, Left-handed completeness for Kleene algebra, via cyclic proofs, (Barthe, Gilles; Sutcliffe, Geoff; Veanes, Margus, LPAR-22. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning. LPAR-22. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, EPiC Series in Computing, vol. 57 (2018), EasyChair), 271-289 · Zbl 1415.68124
[5] Ésik, Zoltán, Group axioms for iteration, Inf. Comput., 148, 2, 131-180 (1999) · Zbl 0924.68143
[6] Foster, Simon; Struth, Georg, On the fine-structure of regular algebra, J. Autom. Reason., 54, 2, 165-197 (2015) · Zbl 1331.68128
[7] Jacobs, Bart, A bialgebraic review of deterministic automata, regular expressions and languages, (Futatsugi, K.; etal., Essays Dedicated to Joseph A. Goguen. Essays Dedicated to Joseph A. Goguen, Lecture Notes in Computer Science, vol. 4060 (2006), Springer), 375-404 · Zbl 1133.68049
[8] Kleene, Stephen C., Representation of events in nerve nets and finite automata, (Shannon, C. E.; McCarthy, J., Automata Studies (1956), Princeton University Press: Princeton University Press Princeton, N.J.), 3-41
[9] Kot, Łucja; Kozen, Dexter, Second-Order Abstract Interpretation Via Kleene Algebra (December 2004), Computer Science Department, Cornell University, Technical Report TR2004-1971
[10] Kot, Łucja; Kozen, Dexter, Kleene algebra and bytecode verification, (Spoto, Fausto, Proc. 1st Workshop Bytecode Semantics, Verification, Analysis, and Transformation. Proc. 1st Workshop Bytecode Semantics, Verification, Analysis, and Transformation, Bytecode’05 (April 2005)), 201-215
[11] Kozen, Dexter, A completeness theorem for Kleene algebras and the algebra of regular events, (Proc. 6th Symp. Logic in Comput. Sci. (July 1991), IEEE: IEEE Amsterdam), 214-225
[12] Kozen, Dexter, A completeness theorem for Kleene algebras and the algebra of regular events, Inf. Comput., 110, 2, 366-390 (May 1994)
[13] Kozen, Dexter; Silva, Alexandra, Left-handed completeness, (Kahl, Wolfram; Griffin, Timothy G., Relational and Algebraic Methods in Computer Science - 13th International Conference, RAMiCS 2012, Cambridge, UK, September 17-20, 2012. Proceedings. Relational and Algebraic Methods in Computer Science - 13th International Conference, RAMiCS 2012, Cambridge, UK, September 17-20, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7560 (2012), Springer), 162-178 · Zbl 1364.68268
[14] Kozen, Dexter; Tiuryn, Jerzy, Substructural logic and partial correctness, Trans. Comput. Log., 4, 3, 355-378 (July 2003)
[15] Krob, Daniel, A complete system of B-rational identities, Theor. Comput. Sci., 89, 2, 207-343 (October 1991)
[16] Rutten, Jan J. M.M., Automata and coinduction (an exercise in coalgebra), (Sangiorgi, Davide; de Simone, Robert, CONCUR. CONCUR, Lecture Notes in Computer Science, vol. 1466 (1998), Springer), 194-218 · Zbl 0940.68085
[17] Rutten, Jan J. M.M., A coinductive calculus of streams, Math. Struct. Comput. Sci., 15, 1, 93-147 (2005) · Zbl 1068.68061
[18] Salomaa, Arto, Two complete axiom systems for the algebra of regular events, J. Assoc. Comput. Mach., 13, 1, 158-169 (January 1966)
[19] Silva, Alexandra, Kleene Coalgebra (2010), University of Nijmegen, PhD thesis · Zbl 1440.68174
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.