Document Open Access Logo

Ambiguity Through the Lens of Measure Theory

Author Olivier Carton

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.34.pdf
  • Filesize: 0.67 MB
  • 14 pages

Document Identifiers

Author Details

Olivier Carton
  • IRIF, Université Paris Cité & CNRS, France

Funding

Work supported by ANR CODYS (ANR-18-CE40-0007).

Cite As Get BibTex

Olivier Carton. Ambiguity Through the Lens of Measure Theory. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.34

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata over infinite objects
Keywords
  • ambiguity
  • Büchi automata
  • measure theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google Scholar
  2. V. Becher and O. Carton. Normal numbers and computer science. In V. Berthé and M. Rigo, editors, Sequences, Groups, and Number Theory, Trends in Mathematics Series, pages 233-269. Birkhäuser, 2018. Google Scholar
  3. J. Berstel and D. Perrin. Theory of Codes. Academic Press, 1984. Google Scholar
  4. J. Berstel and Ch. Reutenauer. Noncommutative Rational Series with Applications. Cambridge University Press, 2010. Google Scholar
  5. É. Borel. Les probabilités dénombrables et leurs applications arithmétiques. Rendiconti Circ. Mat. Palermo, 27:247-271, 1909. Google Scholar
  6. N. Bousquet and Ch. Löding. Equivalence and inclusion problem for strongly unambiguous Büchi automata. In LATA 2010, volume 6031 of Lecture Notes in Computer Science, pages 118-129. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13089-2_10.
  7. M. Boyle and K. Petersen. Entropy of Hidden Markov Processes and Connections to Dynamical Systems, volume 385 of London Mathematical Society Lecture Notes, chapter Hidden Markov processes in the context of symbolic dynamics, pages 5-71. Cambridge University Press, 2011. Google Scholar
  8. P. Brémaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, 2008. Google Scholar
  9. O. Carton. Preservation of normality by unambiguous transducers. CoRR, abs/2006.00891, 2022. URL: http://arxiv.org/abs/2006.00891.
  10. O. Carton and M. Michel. Unambiguous Büchi automata. Theoret. Comput. Sci., 297:37-81, 2003. Google Scholar
  11. Ch. Choffrut and S. Grigorieff. Uniformization of rational relations. In Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pages 59-71. Springer, 1999. Google Scholar
  12. Th. Colcombet. Unambiguity in automata theory. In Descriptional Complexity of Formal Systems, volume 9118 of Lecture Notes in Computer Science, pages 3-18. Springer, 2015. Google Scholar
  13. P. R. Halmos. Lectures on Boolean algebras. Von Nostrand, 1963. Google Scholar
  14. G. Hansel and D. Perrin. Mesures de probabilité rationnelles. In M. Lothaire, editor, Mots, pages 335-357. Hermes, 1990. Google Scholar
  15. M. Holzer and M. Kutrib. Descriptional complexity of (un)ambiguous finite state machines and pushdown automata. In Reachability Problems, pages 1-23. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15349-5_1.
  16. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979. Google Scholar
  17. D. Isaak and Ch. Löding. Efficient inclusion testing for simple classes of unambiguous ω-automata. Inf. Process. Lett., 112(14-15):578-582, 2012. Google Scholar
  18. D. Lind and B. Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995. Google Scholar
  19. D. Perrin and J.-É. Pin. Infinite Words. Elsevier, 2004. Google Scholar
  20. G. Pighizzini. Two-way finite automata: Old and recent results. Electronic Proceedings in Theoretical Computer Science, 90:3-20, 2012. URL: https://doi.org/10.4204/eptcs.90.1.
  21. J. Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Google Scholar
  22. E. Schmidt. Succinctness of descriptions of context-free, regular, and finite languages. DAIMI Report Series, 7(84), 1978. URL: https://doi.org/10.7146/dpb.v7i84.6500.
  23. R. E. Stearns and H. B. Hunt III. On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. SIAM J. Comput., 14(3):598-611, 1985. URL: https://doi.org/10.1137/0214044.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact