License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.34
URN: urn:nbn:de:0030-drops-174269
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17426/
Go to the corresponding LIPIcs Volume Portal

Carton, Olivier

Ambiguity Through the Lens of Measure Theory

pdf-format:
LIPIcs-FSTTCS-2022-34.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{carton:LIPIcs.FSTTCS.2022.34,
  author =	{Carton, Olivier},
  title =	{{Ambiguity Through the Lens of Measure Theory}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17426},
  URN =		{urn:nbn:de:0030-drops-174269},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.34},
  annote =	{Keywords: ambiguity, B\"{u}chi automata, measure theory}
}

Keywords: ambiguity, Büchi automata, measure theory
Collection: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Issue Date: 2022
Date of publication: 14.12.2022

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