Infinitary Axiomatization of the Equational Theory of Context-Free Languages

2013/08/27 by Niels Bjørn Bugge Grathwohl, Fritz Henglein, Dexter Kozen
Computer Science · #Advanced Algebra and Logic #Algebra over a field #Calculus (dental) #Equational logic #Formal Methods in Verification #Interpretation (philosophy) #Model theory #Natural (archaeology) #Property (philosophy) #cs.FL #cs.LO #semigroups and automata theory

paper · pdf · doi:10.4204/eptcs.126.4

published as EPTCS 126, 2013, pp. 44-55 · In Proceedings FICS 2013, arXiv:1308.5896

openalex publication_date 2013/08/27 · arxiv created 2013/09/04 · arxiv updated 2013/09/05 · openalex created_date 2017/05/26 · openalex updated_date 2026/08/06

Abstract

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

Citations

• Proceedings Workshop on Fixed Points in Computer Science
• The Design and Analysis of Algorithms