Document Open Access Logo

Aperiodic Weighted Automata and Weighted First-Order Logic

Authors Manfred Droste, Paul Gastin

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.76.pdf
  • Filesize: 498 kB
  • 15 pages

Document Identifiers

Author Details

Manfred Droste
  • Institut für Informatik, Universität Leipzig, Germany
Paul Gastin
  • LSV, ENS Paris-Saclay, CNRS, Université Paris-Saclay, France

Funding

  • Droste, Manfred: Partly supported by a visiting professorship at ENS Paris-Saclay
  • Gastin, Paul: Partly supported by the DFG Research Training Group QuantLA.

Cite AsGet BibTex

Manfred Droste and Paul Gastin. Aperiodic Weighted Automata and Weighted First-Order Logic. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.76

Abstract

By fundamental results of Schützenberger, McNaughton and Papert from the 1970s, the classes of first-order definable and aperiodic languages coincide. Here, we extend this equivalence to a quantitative setting. For this, weighted automata form a general and widely studied model. We define a suitable notion of a weighted first-order logic. Then we show that this weighted first-order logic and aperiodic polynomially ambiguous weighted automata have the same expressive power. Moreover, we obtain such equivalence results for suitable weighted sublogics and finitely ambiguous or unambiguous aperiodic weighted automata. Our results hold for general weight structures, including all semirings, average computations of costs, bounded lattices, and others.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantitative automata
  • Theory of computation → Logic and verification
Keywords
  • Weighted automata
  • weighted logic
  • aperiodic automata
  • first-order logic
  • unambiguous
  • finitely ambiguous
  • polynomially ambiguous

Metrics

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

Related Versions

References

  1. Parvaneh Babari, Manfred Droste, and Vitaly Perevoshchikov. Weighted register automata and weighted logic on data words. Theor. Comput. Sci., 744:3-21, 2018. Google Scholar
  2. Jean Berstel and Christophe Reutenauer. Rational Series and their Languages. Springer, 1988. Google Scholar
  3. Benedikt Bollig and Paul Gastin. Weighted versus Probabilistic Logics. In Volker Diekert and Dirk Nowotka, editors, International Conference on Developments in Language Theory (DLT'09), volume 5583 of Lecture Notes in Computer Science, pages 18-38. Springer, 2009. Google Scholar
  4. Benedikt Bollig, Paul Gastin, Benjamin Monmege, and Marc Zeitoun. Pebble Weighted Automata and Transitive Closure Logics. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Automata, Languages and Programming, pages 587-598, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  5. Benedikt Bollig, Paul Gastin, Benjamin Monmege, and Marc Zeitoun. Pebble Weighted Automata and Weighted Logics. ACM Transactions on Computational Logic, 15(2):1-35, 2014. Google Scholar
  6. J. Richard Büchi. Weak Second-Order Arithmetic and Finite Automata. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 6:66-92, 1960. Google Scholar
  7. Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Expressiveness and Closure Properties for Quantitative Languages. Logical Methods in Computer Science, 6(3), 2010. Google Scholar
  8. Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Quantitative languages. ACM Trans. Comput. Log., 11(4):23:1-23:38, 2010. Google Scholar
  9. Volker Diekert and Paul Gastin. First-order definable languages. In Jörg Flum, Erich Grädel, and Thomas Wilke, editors, Logic and Automata: History and Perspectives, volume 2 of Texts in Logic and Games, pages 261-306. Amsterdam University Press, 2008. Google Scholar
  10. Manfred Droste and Stefan Dück. Weighted Automata and Logics on Graphs. In Mathematical Foundations of Computer Science (MFCS'15), volume 9234 of Lecture Notes in Computer Science, pages 192-204. Springer, 2015. Google Scholar
  11. Manfred Droste and Stefan Dück. Weighted automata and logics for infinite nested words. Inf. Comput., 253:448-466, 2017. Google Scholar
  12. Manfred Droste and Paul Gastin. Weighted Automata and Weighted Logics. In International Colloquium on Automata, Languages and Programming (ICALP'05), volume 3580 of Lecture Notes in Computer Science, pages 513-525. Springer, 2005. Google Scholar
  13. Manfred Droste and Paul Gastin. Weighted automata and weighted logics. Theor. Comput. Sci., 380(1-2):69-86, 2007. Google Scholar
  14. Manfred Droste and Paul Gastin. Aperiodic Weighted Automata and Weighted First-Order Logic. CoRR, abs/1902.08149, 2019. Google Scholar
  15. Manfred Droste, Werner Kuich, and Heiko Vogler, editors. Handbook of Weighted Automata. Springer Berlin Heidelberg, 2009. Google Scholar
  16. Manfred Droste and Ingmar Meinecke. Weighted automata and weighted MSO logics for average and long-time behaviors. Inf. Comput., 220:44-59, 2012. Google Scholar
  17. Manfred Droste and Vitaly Perevoshchikov. Multi-weighted Automata and MSO Logic. Theory Comput. Syst., 59(2):231-261, 2016. Google Scholar
  18. Manfred Droste and George Rahonis. Weighted automata and weighted logics on infinite words. Izvestiya VUZ. Matematika, 54:26-45, 2010. Google Scholar
  19. Manfred Droste and Heiko Vogler. Weighted tree automata and weighted logics. Theor. Comput. Sci., 366(3):228-247, 2006. Google Scholar
  20. Manfred Droste and Heiko Vogler. Weighted automata and multi-valued logics over arbitrary bounded lattices. Theor. Comput. Sci., 418:14-36, 2012. Google Scholar
  21. Calvin C. Elgot. Decision Problems of Finite Automata Design and Related Arithmetics. Transactions of the American Mathematical Society, 98:21-52, 1961. Google Scholar
  22. Ina Fichtner. Weighted Picture Automata and Weighted Logics. Theory Comput. Syst., 48(1):48-78, 2011. Google Scholar
  23. Paul Gastin and Benjamin Monmege. A unifying survey on weighted logics and weighted automata. Soft Computing, 22(4):1047-1065, December 2018. Google Scholar
  24. Oscar H Ibarra and Bala Ravikumar. On sparseness, ambiguity and other decision problems for acceptors and transducers. In Symposium on Theoretical Aspects of Computer Science (STACS'86), volume 210 of Lecture Notes in Computer Science, pages 171-179. Springer, 1986. Google Scholar
  25. Daniel Kirsten. A Burnside Approach to the Termination of Mohri’s Algorithm for Polynomially Ambiguous Min-Plus-Automata. RAIRO - Theoretical Informatics and Applications, 42(3):553-581, June 2008. Google Scholar
  26. Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoretical Computer Science, 327(3):349-373, November 2004. Google Scholar
  27. Stephan Kreutzer and Cristian Riveros. Quantitative Monadic Second-Order Logic. In Symposium on Logic in Computer Science (LICS'13). IEEE, June 2013. Google Scholar
  28. Werner Kuich and Arto Salomaa. Semirings, Automata, Languages. Springer Berlin Heidelberg, 1986. Google Scholar
  29. Eleni Mandrali and George Rahonis. On weighted first-order logics with discounting. Acta Informatica, 51(2):61-106, January 2014. Google Scholar
  30. Filip Mazowiecki and Cristian Riveros. Pumping Lemmas for Weighted Automata. In Symposium on Theoretical Aspects of Computer Science (STACS'18), volume 96 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1-50:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  31. Filip Mazowiecki and Cristian Riveros. Copyless cost-register automata: Structure, expressiveness, and closure properties. Journal of Computer and System Sciences, 100:1-29, March 2019. Google Scholar
  32. Robert McNaughton and Seymour Papert. Counter-Free Automata. The MIT Press, Cambridge, Mass., 1971. Google Scholar
  33. Erik Paul. On Finite and Polynomial Ambiguity of Weighted Tree Automata. In International Conference on Developments in Language Theory (DLT'16), volume 9840 of Lecture Notes in Computer Science, pages 368-379. Springer, 2016. Google Scholar
  34. Karin Quaas. MSO logics for weighted timed automata. Formal Methods in System Design, 38(3):193-222, 2011. Google Scholar
  35. Christophe Reutenauer. Propriétés arithmétiques et topologiques de séries rationnelles en variables non commutatives. PhD thesis, Université Paris VI, 1977. Google Scholar
  36. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Google Scholar
  37. Jacques Sakarovitch and Rodrigo de Souza. Lexicographic Decomposition of k-Valued Transducers. Theory of Computing Systems, 47(3):758-785, April 2009. Google Scholar
  38. Arto Salomaa and Matti Soittola. Automata-Theoretic Aspects of Formal Power Series. Springer, 1978. Google Scholar
  39. Marcel Paul Schützenberger. On the definition of a family of automata. Information and Control, 4(2-3):245-270, September 1961. Google Scholar
  40. Marcel Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8(2):190-194, 1965. Google Scholar
  41. Boris A. Trakhtenbrot. Finite Automata and Logic of Monadic Predicates. Doklady Akademii Nauk SSSR, 149:326-329, 1961. Google Scholar
  42. Andreas Weber and Helmut Seidl. On the degree of ambiguity of finite automata. Theoretical Computer Science, 88(2):325-349, October 1991. Google Scholar
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 Imprint Privacy Contact