Infinitary Axiomatization of the Equational Theory of Context-Free Languages

Issue title: Fixed Points in Computer Science (FICS) 2013

Guest editors: David Baelde, Arnaud Carayol, Ralph Matthes and Igor Walukiewicz

Article type: Research Article

Authors: Grathwohl, Niels Bjørn Bugge^{a; *; C} | Henglein, Fritz^{b; *} | Kozen, Dexter^{c; †}

Affiliations: [a] Department of Computer Science (DIKU), University of Copenhagen, Denmark. bugge@diku.dk | [b] Department of Computer Science (DIKU), University of Copenhagen, Denmark. henglein@diku.dk | [c] Department of Computer Science, Cornell University, USA. kozen@cs.cornell.edu

Correspondence: [C] Address for correspondence: Department of Computer Science (DIKU), University of Copenhagen, Denmark

Note: [*] The DIKU-affiliated authors express their thanks to the Department of Computer Science at Cornell University for hosting them in the Spring 2013 and to the Danish Council for Independent Research for financial support for this work under Project 11-106278, “Kleene Meets Church (KMC): Regular Expressions and Types.”.

Note: [†] Research supported by the National Security Agency.

Abstract: We give a natural complete infinitary axiomatization of the equational theory of the context-free languages, answering a question of Leiß (1992).

Keywords: Context free languages, Kleene algebra, algebraically complete semirings, Conway semirings, μ-semiring

DOI: 10.3233/FI-2017-1469

Journal: Fundamenta Informaticae, vol. 150, no. 3-4, pp. 241-257, 2017