Infinitary Axiomatization of the Equational Theory of Context-Free Languages

Reference. Infinitary Axiomatization of the Equational Theory of Context-Free Languages

Niels Bjørn Bugge Grathwohl, Fritz Henglein, Dexter Kozen · EPTCS · 2013 · parsing · DOI

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

Cite

Cite as @grathwohl_infinitary_2013 (helia, typst) · \cite{grathwohl_infinitary_2013} (LaTeX)

BibTeX

bibtex · 16 lines

@article{grathwohl_infinitary_2013,
 title = {Infinitary {Axiomatization} of the {Equational} {Theory} of {Context}-{Free} {Languages}},
 author = {Grathwohl, Niels Bjørn Bugge and Henglein, Fritz and Kozen, Dexter},
 year = {2013},
 doi = {10.4204/EPTCS.126.4},
 url = {http://arxiv.org/abs/1309.0893},
 urldate = {2023-11-28},
 journal = {Electronic Proceedings in Theoretical Computer Science},
 volume = {126},
 pages = {44--55},
 keywords = {Computer Science - Formal Languages and Automata Theory, Computer Science - Logic in Computer Science},
 note = {arXiv:1309.0893 [cs]},
 month = {August},
 abstract = {We give a natural complete infinitary axiomatization of the equational theory of the context-free languages, answering a question of Lei\{{\textbackslash}ss\} (1992).},
 issn = {2075-2180}
}

hayagriva YAML (typst)

yaml · 21 lines

grathwohl_infinitary_2013:
  type: article
  title: Infinitary {Axiomatization} of the {Equational} {Theory} of {Context}-{Free} {Languages}
  author:
  - Grathwohl, Niels Bjørn Bugge
  - Henglein, Fritz
  - Kozen, Dexter
  date: 2013-08
  page-range: 44-55
  url:
    value: http://arxiv.org/abs/1309.0893
    date: 2023-11-28
  serial-number:
    doi: 10.4204/EPTCS.126.4
    issn: 2075-2180
  note: arXiv:1309.0893 [cs]
  abstract: We give a natural complete infinitary axiomatization of the equational theory of the context-free languages, answering a question of Lei\{{\\}ss\} (1992).
  parent:
    type: periodical
    title: Electronic Proceedings in Theoretical Computer Science
    volume: 126

Download: grathwohl_infinitary_2013.bib · grathwohl_infinitary_2013.yml

Cited by (1)

A typed, algebraic approach to parsing krishnaswami_typed_2019PLDI · 2019

In this paper, we recall the definition of the context-free expressions (or µ-regular expressions), an algebraic presentation of the context-free languages. Then, we define a core type system for the context-free expressions which gives a compositional criterion for identifying those context-free expressions which can be parsed unambiguously by predictive algorithms in the style of recursive descent or LL(1). Next, we show how these typed grammar expressions can be used to derive a parser combinator library which both guarantees linear-time parsing with no backtracking and single-token lookahead, and which respects the natural denotational semantics of context-free expressions. Finally, we show how to exploit the type information to write a staged version of this library, which produces dramatic increases in performance, even outperforming code generated by the standard parser generator tool ocamlyacc.

DOI · pldb

Cites 14 works (2 here)

With notes (2)

Towards Kleene Algebra with recursion leis_towards_1992CSL · 1992

We extend Kozen’s theory KA of Kleene Algebra to axiomatize parts of the equational theory of context-free languages, using a least fixed-point operator μ instead of Kleene’s iteration operator*.

DOI

Definable operations in general algebras, and the theory of automata and flowcharts Bekić1984Programming languages and their definition: H. Bekič (1936–1982) · 1984

We study the class of operations definable from the given operations of an algebra of sets by union, composition, and fixed points; we obtain two theorems on definable operations that give us as special case the regular-equals-recognisable theorem of generalised finite automata theory. Definable operations arise also as the operations computable by charts; by translating into predicate logic, we obtain Manna’s formulas for termination and correctness of flowcharts.

DOI

External (12)

The Algebraic Approach I: The Algebraization of the Chomsky Hierarchy (2008)
The Algebraic Approach II: Dioids, Quantales and Monads (2008)
Modern automata theory (Ésik, Kuich; unpublished manuscript) (2007)
Algebraically Complete Semirings and Greibach Normal Form (2005)
Greibach Normal Form in Algebraically Complete Semirings (2002)
The Formal Semantics of Programming Languages (1993)
The Design and Analysis of Algorithms (1991)
Equivalences and Transformations of Regular Systems – Applications to Recursive Program Schemes and Grammars (1986)
The Lambda Calculus: Its Syntax and Semantics (1984)
Results on the propositional [mu]-calculus (1983)
On Induction vs. *-Continuity (1981)
A characterization of context-free languages (1971)