Infinitary Axiomatization of the Equational Theory of Context-Free Languages

Abstract

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

@inproceedings{GHK13a,
  abstract = {We give a natural complete infinitary axiomatization of the equational
            theory of the context-free languages, answering a question of Lei{\ss} (1992).},
  address = {Torino, Italy},
  author = {Niels Bj{\o}rn Bugge Grathwohl, Fritz Henglein, and Dexter Kozen},
  booktitle = {Proc.~9th Workshop Fixed Points in Computer Science (FICS 2013)},
  editor = {David Baelde and Arnaud Carayol},
  month = {September},
  number = {{\url{http://arxiv.org/abs/1309.0893}}},
  doi = {10.4204/EPTCS.126.4},
  pages = {44--55},
  series = {Electronic Proceedings in Theoretical Computer Science},
  title = {Infinitary Axiomatization of the Equational Theory of Context-Free Languages},
  volume = {126},
  year = {2013},
}