Paper Info
Title
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 lan- guages, 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.
Year
DOI
Venue
2008
10.4230/LIPIcs.FSTTCS.2008.1743
FSTTCS
Keywords
Field
DocType
regular language,context free language,pushdown automata,boolean algebra
Deterministic context-free grammar,Discrete mathematics,Combinatorics,Context-free language,Nested word,Computer science,Abstract family of languages,Deterministic pushdown automaton,Deterministic context-free language,Cone (formal languages),Pumping lemma for regular languages
Conference
Citations 
PageRank 
References 
5
0.53
2
Authors
1
Name
Order
Citations
PageRank
Didier Caucal147039.15