{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T05:20:27Z","timestamp":1776316827107,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540610427","type":"print"},{"value":"9783540498742","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61042-1_35","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:11:41Z","timestamp":1330290701000},"page":"14-33","source":"Crossref","is-referenced-by-count":22,"title":["Kleene algebra with tests and commutativity conditions"],"prefix":"10.1007","author":[{"given":"Dexter","family":"Kozen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"2_CR1","unstructured":"Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1975."},{"key":"2_CR2","unstructured":"S. Anderaa. On the algebra of regular expressions. Appl. Math., pages 1\u201318, January 1965."},{"key":"2_CR3","unstructured":"K. V. Archangelsky. A new finite complete solvable quasiequational calculus for algebra of regular languages. Manuscript, Kiev State University, 1992."},{"key":"2_CR4","unstructured":"Roland Carl Backhouse. Closure Algorithms and the Star-Height Problem of Regular Languages. PhD thesis, Imperial College, 1975."},{"key":"2_CR5","unstructured":"Stephen L. Bloom and Zolt\u00e1n \u00e9sik. Equational axioms for regular sets. Technical Report 9101, Stevens Institute of Technology, May 1991."},{"issue":"4","key":"2_CR6","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1051\/ita\/1990240404191","volume":"24","author":"M. Boffa","year":"1990","unstructured":"Maurice Boffa. Une remarque sur les syst\u00e8mes complets d'identit\u00e9s rationnelles. Informatique th\u00e9oretique et Applications\/Theoretical Informatics and Applications, 24(4):419\u2013423, 1990.","journal-title":"Informatique th\u00e9oretique et Applications"},{"issue":"5","key":"2_CR7","first-page":"366","volume":"9","author":"C. B\u00f6hm","year":"1966","unstructured":"C. B\u00f6hm and G. Jacopini. Flow diagrams, Turing machines, and languages with only two formation rules. Comm. Assoc. Comput. Mach., 9(5):366\u2013371, May 1966.","journal-title":"Comm. Assoc. Comput. Mach."},{"key":"2_CR8","unstructured":"Ernie Cohen, February 1994. Personal communication."},{"key":"2_CR9","unstructured":"Ernie Cohen. Hypotheses in Kleene algebra. ftp:\/\/ftp.bellcore.com\/pub\/ernie\/research\/homepage.html, April 1994."},{"key":"2_CR10","unstructured":"Ernie Cohen. Lazy caching. ftp:\/\/ftp.bellcore.com\/pub\/ernie\/research\/homepage.html, 1994."},{"key":"2_CR11","unstructured":"Ernie Cohen. Using Kleene algebra to reason about concurrency control. ftp:\/\/ftp.bellcore.com\/pub\/ernie\/research\/homepage.html, 1994."},{"key":"2_CR12","unstructured":"John Horton Conway. Regular Algebra and Finite Machines. Chapman and Hall, 1971."},{"issue":"2","key":"2_CR13","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/0022-0000(79)90046-1","volume":"18","author":"M. J. Fischer","year":"1979","unstructured":"Michael J. Fischer and Richard E. Ladner. Prepositional dynamic logic of regular programs. J. Comput. Syst. Sci., 18(2):194\u2013211, 1979.","journal-title":"J. Comput. Syst. Sci."},{"issue":"7","key":"2_CR14","first-page":"379","volume":"23","author":"D. Harel","year":"1980","unstructured":"David Harel. On folk theorems. Comm. Assoc. Comput. Mach., 23(7):379\u2013389, July 1980.","journal-title":"Comm. Assoc. Comput. Mach."},{"issue":"2","key":"2_CR15","first-page":"55","volume":"21","author":"K. Hirose","year":"1972","unstructured":"K. Hirose and M. Oya. General theory of flowcharts. Comment. Math. Univ. St. Pauli, 21(2):55\u201371, 1972.","journal-title":"Comment. Math. Univ. St. Pauli"},{"key":"2_CR16","unstructured":"John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979."},{"issue":"5","key":"2_CR17","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1137\/0219061","volume":"19","author":"K. Iwano","year":"1990","unstructured":"Kazuo Iwano and Kenneth Steiglitz. A semiring on convex polygons and zero-sum cycle problems. SIAM J. Comput., 19(5):883\u2013901, 1990.","journal-title":"SIAM J. Comput."},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Stephen C. Kleene. Representation of events in nerve nets and finite automata. In Shannon and McCarthy, editors, Automata Studies, pages 3\u201341. Princeton University Press, 1956.","DOI":"10.1515\/9781400882618-002"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Dexter Kozen. On induction vs. *-continuity. In Kozen, editor, Proc. Workshop on Logic of Programs, volume 131 of Ltd. Notes in Comput. Sci., pages 167\u2013176. Springer, 1981.","DOI":"10.1007\/BFb0025782"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Dexter Kozen. On Kleene algebras and closed semirings. In Rovan, editor, Proc. Math. Found. Comput. Sci., volume 452 of Lect. Notes in Comput. Sci., pages 26\u201347. Springer, 1990.","DOI":"10.1007\/BFb0029594"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Dexter Kozen. The Design and Analysis of Algorithms. Springer, 1991.","DOI":"10.1007\/978-1-4612-4400-4"},{"issue":"2","key":"2_CR22","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1006\/inco.1994.1037","volume":"110","author":"D. Kozen","year":"1994","unstructured":"Dexter Kozen. A completeness theorem for Kleene algebras and the algebra of regular events. Infor. and Comput., 110(2):366\u2013390, May 1994.","journal-title":"Infor. and Comput."},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Dexter Kozen and Jerzy Tiuryn. Logics of programs. In van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 789\u2013840. North Holland, 1990.","DOI":"10.1016\/B978-0-444-88074-1.50019-6"},{"issue":"2","key":"2_CR24","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0304-3975(91)90395-I","volume":"89","author":"D. Krob","year":"1991","unstructured":"Daniel Krob. A complete system of B-rational identities. Theoretical Computer Science, 89(2):207\u2013343, October 1991.","journal-title":"Theoretical Computer Science"},{"key":"2_CR25","doi-asserted-by":"crossref","unstructured":"Werner Kuich. The Kleene and Parikh theorem in complete semirings. In Ottmann, editor, Proc. 14th Colloq. Automata, Languages, and Programming, volume 267 of Lect. Notes in Comput. Sci., pages 212\u2013225. EATCS, Springer, 1987.","DOI":"10.1007\/3-540-18088-5_17"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"Werner Kuich and Arto Salomaa. Semirings, Automata, and Languages. Springer, 1986.","DOI":"10.1007\/978-3-642-69959-7"},{"key":"2_CR27","unstructured":"G. Mirkowska. Algorithmic Logic and its Applications. PhD thesis, University of Warsaw, 1972. In Polish."},{"key":"2_CR28","volume-title":"PhD thesis","author":"K. C. Ng","year":"1984","unstructured":"K. C. Ng. Relation Algebras with Transitive Closure. PhD thesis, University of California, Berkeley, 1984."},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"Vaughan Pratt. Dynamic algebras as a well-behaved fragment of relation algebras. In D. Pigozzi, editor, Proc. Conf. Algebra and Computer Science, volume 425 of Lect. Notes in Comput. Sci., pages 77\u2013110. Springer, June 1988.","DOI":"10.1007\/BFb0043079"},{"key":"2_CR30","unstructured":"Vaughan Pratt. Action logic and pure induction. In J. van Eijck, editor, Proc. Logics in AI: European Workshop JELIA '90, volume 478 of Lect. Notes in Comput. Sci., pages 97\u2013120. Springer, September 1990."},{"key":"2_CR31","first-page":"120","volume":"16","author":"V. N. Redko","year":"1964","unstructured":"V. N. Redko. On defining relations for the algebra of regular events. Ukrain. Mat. Z., 16:120\u2013126, 1964. In Russian.","journal-title":"Ukrain. Mat. Z."},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Jacques Sakarovitch. Kleene's Theorem revisited: a formal path from Kleene to Chomsky. In A. Kelemenova and J. Keleman, editors, Trends, Techniques, and Problems in Theoretical Computer Science, volume 281 of Lect. Notes in Computer Science, pages 39\u201350. Springer, 1987.","DOI":"10.1007\/3540185356_29"},{"issue":"1","key":"2_CR33","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1145\/321312.321326","volume":"13","author":"A. Salomaa","year":"1966","unstructured":"Arto Salomaa. Two complete axiom systems for the algebra of regular events. J. Assoc. Comput. Mach., 13(1):158\u2013169, January 1966.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"2_CR34","doi-asserted-by":"crossref","first-page":"65","DOI":"10.2307\/2268577","volume":"6","author":"A. Tarski","year":"1941","unstructured":"A. Tarski. On the calculus of relations. J. Symb. Logic, 6(3):65\u2013106, 1941.","journal-title":"J. Symb. Logic"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61042-1_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:03:30Z","timestamp":1605647010000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61042-1_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540610427","9783540498742"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/3-540-61042-1_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}