License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.1
URN: urn:nbn:de:0030-drops-33862
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3386/
Go to the corresponding LIPIcs Volume Portal

Colcombet, Thomas

Forms of Determinism for Automata (Invited Talk)

pdf-format:
2.pdf (0.9 MB)

Abstract

We survey in this paper some variants of the notion of determinism, refining the spectrum between non-determinism and determinism. We present unambiguous automata, strongly unambiguous automata, prophetic automata, guidable automata, and history-deterministic automata. We instantiate these various notions for finite words, infinite words, finite trees, infinite trees, data languages, and cost functions. The main results are underlined and some open problems proposed.

BibTeX - Entry

@InProceedings{colcombet:LIPIcs:2012:3386,
  author =	{Thomas Colcombet},
  title =	{{Forms of Determinism for Automata (Invited Talk)}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{1--23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3386},
  URN =		{urn:nbn:de:0030-drops-33862},
  doi =		{10.4230/LIPIcs.STACS.2012.1},
  annote =	{Keywords: Automata, determinism, unambiguity, words, infinite trees}
}

Keywords: Automata, determinism, unambiguity, words, infinite trees
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI