Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Caucal, Didier http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-17436
URL:

Boolean algebras of unambiguous context-free languages

pdf-format:


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.

BibTeX - Entry

@InProceedings{caucal:LIPIcs:2008:1743,
  author =	{Didier Caucal},
  title =	{{Boolean algebras of unambiguous context-free languages}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{83--94},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Ramesh Hariharan and Madhavan Mukund and V Vinay},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1743},
  URN =		{urn:nbn:de:0030-drops-17436},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2008.1743},
  annote =	{Keywords: Synchronization, deterministic graph grammars}
}

Keywords: Synchronization, deterministic graph grammars
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue date: 2008
Date of publication: 2008


DROPS-Home | Fulltext Search | Imprint Published by LZI