LIPIcs.FSTTCS.2008.1743.pdf
- Filesize: 437 kB
- 12 pages
Document
Boolean algebras of unambiguous context-free languages
Author
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2008-12-05
Cite AsGet BibTex
Didier Caucal. Boolean algebras of unambiguous context-free languages. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 83-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1743
https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1743
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.
Keywords
- Synchronization
- deterministic graph grammars
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads