Skip to Main content Skip to Navigation
Conference papers

Boolean algebras of unambiguous context-free languages

Abstract : Several recent works have studied subfamilies of deterministic context-free languages with good closure properties, for instance the families of input-driven or visibly pushdown languages, or more generally families of languages accepted by pushdown automata whose stack height can be uniquely determined by the input word read so far. These ideas can be described as a notion of synchronization. In this paper we present an extension of synchronization to all context-free languages using graph grammars. This generalization allows one to define boolean algebras of non-deterministic but unambiguous context-free languages containing regular languages.
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00867574
Contributor : Didier Caucal <>
Submitted on : Monday, September 30, 2013 - 7:37:52 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Tuesday, December 31, 2013 - 4:25:12 AM

File

nonambi.pdf
Files produced by the author(s)

Identifiers

Citation

Didier Caucal. Boolean algebras of unambiguous context-free languages. FSTTCS 2008, Dec 2008, Bangalore, India. pp.83-94, ⟨10.4230/LIPIcs.FSTTCS.2008.1743⟩. ⟨hal-00867574⟩

Share

Metrics

Record views

427

Files downloads

120