LIPIcs.STACS.2012.1.pdf
- Filesize: 0.94 MB
- 23 pages
Document
Forms of Determinism for Automata (Invited Talk)
Author
-
Part of:
Volume:
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2012-02-24
Cite As Get BibTex
Thomas Colcombet. Forms of Determinism for Automata (Invited Talk). In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.STACS.2012.1
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.
Subject Classification
Keywords
- Automata
- determinism
- unambiguity
- words
- infinite trees
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads