2026-08-14T17:47:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3386 2024-03-06T10:34:08Z ddc:004 open_access

Forms of Determinism for Automata (Invited Talk) Colcombet, Thomas Automata determinism unambiguity words infinite trees 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Colcombet 2012 Is Part Of LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2012.1 urn:nbn:de:0030-drops-33862 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.1 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode