×

zbMATH — the first resource for mathematics

Left-handed completeness. (English) Zbl 1364.68268
Kahl, Wolfram (ed.) et al., Relational and algebraic methods in computer science. 13th international conference, RAMiCS 2012, Cambridge, UK, September 17–20, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-33313-2/pbk). Lecture Notes in Computer Science 7560, 162-178 (2012).
Summary: We give a new, significantly shorter proof of the completeness of the left-handed star rule of Kleene algebra. The proof exposes the rich interaction of algebra and coalgebra in the theory of Kleene algebra.
For the entire collection see [Zbl 1246.68043].

MSC:
68Q70 Algebraic theory of languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Boffa, M.: Une condition impliquant toutes les identités rationnelles. Informatique Théorique et Applications/Theoretical Informatics and Applications 29(6), 515–518 (1995) · Zbl 0881.68071
[2] Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. In: Mathematical Theory of Automata. MRI Symposia Series, vol. 12, pp. 529–561. Polytechnic Press, Polytechnic Institute of Brooklyn, N.Y (1962)
[3] Conway, J.H.: Regular Algebra and Finite Machines. Chapman and Hall, London (1971) · Zbl 0231.94041
[4] Ésik, Z.: Group axioms for iteration. Inf. Comput. 148(2), 131–180 (1999) · Zbl 0924.68143 · doi:10.1006/inco.1998.2746
[5] Jacobs, B.: A Bialgebraic Review of Deterministic Automata, Regular Expressions and Languages. In: Futatsugi, K., Jouannaud, J.-P., Meseguer, J. (eds.) Goguen Festschrift. LNCS, vol. 4060, pp. 375–404. Springer, Heidelberg (2006) · Zbl 1133.68049 · doi:10.1007/11780274_20
[6] Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp. 3–41. Princeton University Press, Princeton (1956)
[7] Kot, Ł., Kozen, D.: Second-order abstract interpretation via Kleene algebra. Technical Report TR2004-1971, Computer Science Department, Cornell University (December 2004)
[8] Kot, Ł., Kozen, D.: Kleene algebra and bytecode verification. In: Spoto, F. (ed.) Proc. 1st Workshop Bytecode Semantics, Verification, Analysis, and Transformation (Bytecode 2005), pp. 201–215 (April 2005) · doi:10.1016/j.entcs.2005.02.028
[9] Kozen, D.: A completeness theorem for Kleene algebras and the algebra of regular events. Infor. and Comput. 110(2), 366–390 (1994) · Zbl 0806.68082 · doi:10.1006/inco.1994.1037
[10] Kozen, D., Silva, A.: Left-handed completeness. Technical Report, Computing and Information Science, Cornell University (August 2011), http://hdl.handle.net/1813/23556 · Zbl 1364.68268
[11] Kozen, D., Tiuryn, J.: Substructural logic and partial correctness. Trans. Computational Logic 4(3), 355–378 (2003) · Zbl 1365.68327 · doi:10.1145/772062.772066
[12] Krob, D.: A complete system of B-rational identities. Theoretical Computer Science 89(2), 207–343 (1991) · Zbl 0737.68053 · doi:10.1016/0304-3975(91)90395-I
[13] Rutten, J.J.M.M.: Automata and Coinduction (An Exercise in Coalgebra). In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 194–218. Springer, Heidelberg (1998) · Zbl 0940.68085 · doi:10.1007/BFb0055624
[14] Rutten, J.J.M.M.: A coinductive calculus of streams. Mathematical Structures in Computer Science 15(1), 93–147 (2005) · Zbl 1068.68061 · doi:10.1017/S0960129504004517
[15] Salomaa, A.: Two complete axiom systems for the algebra of regular events. J. Assoc. Comput. Mach. 13(1), 158–169 (1966) · Zbl 0149.24902 · doi:10.1145/321312.321326
[16] Silva, A.: Kleene Coalgebra. PhD thesis, University of Nijmegen (2010) · 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.