Document Open Access Logo

Maximal Partition Logic: Towards a Logical Characterization of Copyless Cost Register Automata

Authors Filip Mazowiecki, Cristian Riveros

PDF
Thumbnail PDF

File

LIPIcs.CSL.2015.144.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Filip Mazowiecki
Cristian Riveros

Cite As Get BibTex

Filip Mazowiecki and Cristian Riveros. Maximal Partition Logic: Towards a Logical Characterization of Copyless Cost Register Automata. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 144-159, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CSL.2015.144

Abstract

It is highly desirable for a computational model to have a logic characterization like in the seminal work from Buchi that connects MSO with finite automata. For example, weighted automata are the quantitative extension of finite automata for computing functions over words and they can be naturally characterized by a subframent of weighted logic introduced by Droste and Gastin. Recently, cost register automata (CRA) were introduced by Alur et al. as an alternative model for weighted automata. In hope of finding decidable subclasses of weighted automata, they proposed to restrict their model with the so-called copyless restriction. Unfortunately, copyless CRA do not enjoy good closure properties and, therefore, a logical characterization of this class seems to be unlikely.

In this paper, we introduce a new logic called maximal partition logic (MPL) for studying the expressiveness of copyless CRA. In contrast from the previous approaches (i.e. weighted logics), MPL is based on a new set of "regular" quantifiers that partition a word into maximal subwords, compute the output of a subformula over each subword separately, and then aggregate these outputs with a semiring operation. We study the expressiveness of MPL and compare it with weighted logics. Furthermore, we show that MPL is equally expressive to a natural subclass of copyless CRA. This shows the first logical characterization of copyless CRA and it gives a better understanding of the copyless restriction in weighted automata.

Subject Classification

Keywords
  • MSO
  • Finite Automata
  • Cost Register Automata
  • Weighted Automata
  • Weighted Logics
  • Semirings

Metrics

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

References

  1. V Alfred. Algorithms for finding patterns in strings. Handbook of Theoretical Computer Science: Algorithms and complexity, 1:255, 1990. Google Scholar
  2. Shaull Almagor, Udi Boker, and Orna Kupferman. What’s decidable about weighted automata? In ATVA, pages 482-491, 2011. Google Scholar
  3. Rajeev Alur, Loris D'Antoni, Jyotirmoy Deshmukh, Mukund Raghothaman, and Yifei Yuan. Regular functions and cost register automata. In Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 13-22. IEEE Computer Society, 2013. Google Scholar
  4. Benedikt Bollig, Paul Gastin, Benjamin Monmege, and Marc Zeitoun. Logical characterization of weighted pebble walking automata. In Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), page 19. ACM, 2014. Google Scholar
  5. Thomas Colcombet, Clemens Ley, and Gabriele Puppis. On the use of guards for logics with data. In Mathematical Foundations of Computer Science 2011, pages 243-255. Springer, 2011. Google Scholar
  6. Karel Culik II and Jarkko Kari. Image compression using weighted finite automata. In Mathematical Foundations of Computer Science 1993, pages 392-402. Springer, 1993. Google Scholar
  7. Manfred Droste and Paul Gastin. Weighted automata and weighted logics. Theor. Comput. Sci., 380(1-2):69-86, 2007. Google Scholar
  8. Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata. Springer, 1st edition, 2009. Google Scholar
  9. Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. Spanners: a formal framework for information extraction. In Proceedings of the 32nd symposium on Principles of database systems, pages 37-48. ACM, 2013. Google Scholar
  10. Jeffrey Friedl. Mastering regular expressions. " O'Reilly Media, Inc.", 2006. Google Scholar
  11. John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. Google Scholar
  12. Benny Kimelfeld. Database principles in information extraction. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 156-163. ACM, 2014. Google Scholar
  13. Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theor. Comput. Sci., 327(3):349-373, 2004. Google Scholar
  14. Stephan Kreutzer and Cristian Riveros. Quantitative monadic second-order logic. In Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 113-122. IEEE Computer Society, 2013. Google Scholar
  15. Daniel Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. In ICALP, pages 101-112, 1992. Google Scholar
  16. Leonid Libkin. Elements of finite model theory. Springer Science & Business Media, 2004. Google Scholar
  17. Filip Mazowiecki and Cristian Riveros. On the expressibility of copyless cost register automata. CoRR, abs/1504.01709, 2015. Google Scholar
  18. Mehryar Mohri. Finite-state transducers in language and speech processing. Computational Linguistics, 23(2):269-311, 1997. Google Scholar
  19. Christos H. Papadimitriou. Computational complexity. Addison-Wesley, 1993. Google Scholar
  20. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Google Scholar
  21. M. P. Schützenberger. On the definition of a family of automata. Information and Control, 4:245-270, 1961. 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 About DROPS Imprint Privacy Contact