2026-07-22T14:20:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17426 2024-03-06T10:59:43Z ddc:004 open_access

Ambiguity Through the Lens of Measure Theory Carton, Olivier ambiguity Büchi automata measure theory In this paper, we establish a strong link between the ambiguity for finite words of a Büchi automaton and the ambiguity for infinite words of the same automaton. This link is based on measure theory. More precisely, we show that such an automaton is unambiguous, in the sense that no finite word labels two runs with the same starting state and the same ending state if and only if for each state, the set of infinite sequences labelling two runs starting from that state has measure zero. The measure used to define these negligible sets, that is sets of measure zero, can be any measure computed by a weighted automaton which is compatible with the Büchi automaton. This latter condition is very natural: the measure must only put weight on sets wA^ℕ where w is the label of some run in the Büchi automaton. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Olivier Carton 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.34 urn:nbn:de:0030-drops-174269 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.34 eng https://creativecommons.org/licenses/by/4.0/legalcode