Document Open Access Logo

Determinisation of Finitely-Ambiguous Copyless Cost Register Automata

Authors Théodore Lopez , Benjamin Monmege , Jean-Marc Talbot

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2019.75.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantitative automata
Keywords
  • Cost-register automata
  • Look-ahead removal
  • Unambiguity
  • Determinisation

Metrics

Abstract

Cost register automata (CRA) are machines reading an input word while computing values using write-only registers: values from registers are combined using the two operations, as well as the constants, of a semiring. Particularly interesting is the subclass of copyless CRAs where the content of a register cannot be used twice for updating the registers. Originally deterministic, non-deterministic variant of CRA may also be defined: the semantics is then obtained by combining the values of all accepting runs with the additive operation of the semiring (as for weighted automata). We show that finitely-ambiguous copyless non-deterministic CRAs (i.e. the ones that admit a bounded number of accepting runs on every input word) can be effectively transformed into an equivalent copyless (deterministic) CRA, without requiring any specific property on the semiring. As a corollary, this also shows that regular look-ahead can effectively be removed from copyless CRAs.

Cite As Get BibTex

Théodore Lopez, Benjamin Monmege, and Jean-Marc Talbot. Determinisation of Finitely-Ambiguous Copyless Cost Register Automata. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 75:1-75:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.75

Author Details

Théodore Lopez
  • Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France
Benjamin Monmege
  • Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France
Jean-Marc Talbot
  • Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France

Funding

This work has been funded by the DeLTA project (ANR-16-CE40-0007).

References

  1. Shaull Almagor, Michaël Cadilhac, Filip Mazowiecki, and Guillermo A. Pérez. Weak Cost Register Automata Are Still Powerful. In Proceedings of the 22nd International Conference on Developments in Language Theory (DLT 2018), volume 11088 of LNCS, pages 83-95. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-98654-8_7.
  2. Rajeev Alur and Loris D'antoni. Streaming Tree Transducers. Journal of the ACM, 64(5):1-55, August 2017. URL: https://doi.org/10.1145/3092842.
  3. Rajeev Alur, Loris D'Antoni, Jyotirmoy V. Deshmukh, Mukund Raghothaman, and Yifei Yuan. Regular Functions and Cost Register Automata. In Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2013), pages 13-22. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/LICS.2013.65.
  4. Rajeev Alur, Emmanuel Filiot, and Ashutosh Trivedi. Regular Transformations of Infinite Strings. In Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science (LICS 2012), pages 65-74. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/LICS.2012.18.
  5. Rajeev Alur and Mukund Raghothaman. Decision Problems for Additive Regular Functions. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, Part II (ICALP 2013), volume 7966 of LNCS, pages 37-48. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-39212-2_7.
  6. Marcella Anselmo. Two-Way Automata with Multiplicity. In Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP 1990), volume 443 of LNCS, pages 88-102. Springer, 1990. Google Scholar
  7. Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Alternating Weighted Automata. In Proceedings of the 17th International Conference on Fundamentals of computation theory (FCT'09), volume 5699 of Lecture Notes in Computer Science, pages 3-13, 2009. Google Scholar
  8. Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Quantitative languages. ACM Transactions on Computational Logic, 11(4), 2010. URL: https://doi.org/10.1145/1805950.1805953.
  9. Laure Daviaud, Pierre-Alain Reynier, and Jean-Marc Talbot. A Generalised Twinning Property for Minimisation of Cost Register Automata. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '16), pages 857-866. ACM, 2016. URL: https://doi.org/10.1145/2933575.2934549.
  10. Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata. Springer, 2009. Google Scholar
  11. Kosaburo Hashiguchi, Kenichi Ishiguro, and Shuji Jimbo. Decidability of The Equivalence Problem for Finitely Ambiguous Finance Automata. International Journal of Algebra and Computation, 12(3):445, 2002. URL: https://doi.org/10.1142/S0218196702000845.
  12. Peter Kostolányi and Filip Misún. Alternating weighted automata over commutative semirings. Theoretical Computer Science, 740:1-27, 2018. URL: https://doi.org/10.1016/j.tcs.2018.05.003.
  13. 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), volume 41 of LIPIcs, pages 144-159. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.CSL.2015.144.
  14. 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. URL: https://doi.org/10.1016/j.jcss.2018.07.002.
  15. Mehryar Mohri, Fernando C. N. Pereira, and Michael Riley. The Design Principles of a Weighted Finite-State Transducer Library. Theoretical Computer Science, 231(1):17-32, 2000. URL: https://doi.org/10.1016/S0304-3975(99)00014-6.
  16. Azaria Paz. Some Aspects of Probabilistic Automata. Information and Computation, 9(1):26-60, 1966. Google Scholar
  17. Michael O. Rabin. Probabilistic Automata. Information and Control, 6(3):230-245, 1963. Google Scholar
  18. Marcel Paul Schützenberger. On the Definition of a Family of Automata. Information and Control, 4(2-3):245-270, 1961. URL: https://doi.org/10.1016/S0019-9958(61)80020-X.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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