Document Open Access Logo

Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties

Authors Filip Mazowiecki, Cristian Riveros

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.53.pdf
  • Filesize: 0.63 MB
  • 13 pages

Document Identifiers

Author Details

Filip Mazowiecki
Cristian Riveros

Cite As Get BibTex

Filip Mazowiecki and Cristian Riveros. Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 53:1-53:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.53

Abstract

Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed by Alur et al. as a new model for computing functions over strings. We study structural properties, expressiveness, and closure properties of copyless CRA. We show that copyless CRA are strictly less expressive than weighted automata and are not closed under reverse operation. To find a better class we impose restrictions on copyless CRA, which ends successfully with a new robust computational model that is closed under reverse and other extensions.

Subject Classification

Keywords
  • Cost Register Automata
  • Weighted Automata
  • Semirings

Metrics

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

References

  1. Shaull Almagor, Udi Boker, and Orna Kupferman. What’s decidable about weighted automata? In ATVA, pages 482-491, 2011. URL: http://dx.doi.org/10.1007/978-3-642-24372-1_37.
  2. Rajeev Alur, Loris D'Antoni, Jyotirmoy Deshmukh, Mukund Raghothaman, and Yifei Yuan. Regular functions and cost register automata. In LICS, pages 13-22. IEEE Computer Society, 2013. Google Scholar
  3. Rajeev Alur and Loris D’Antoni. Streaming tree transducers. In Automata, Languages, and Programming, pages 42-53. Springer, 2012. Google Scholar
  4. Rajeev Alur and Mukund Raghothaman. Decision problems for additive regular functions. In Automata, Languages, and Programming, pages 37-48. Springer, 2013. Google Scholar
  5. J. Richard Buchi. Weak second-order arithmetic and finite automata. Mathematical Logic Quarterly, 6(1-6):66-92, 1960. 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. Joost Engelfriet. Top-down tree transducers with regular look-ahead. Mathematical Systems Theory, 10(1):289-303, 1976. Google Scholar
  10. Joost Engelfriet and Sebastian Maneth. Macro tree transducers, attribute grammars, and mso definable tree translations. Information and Computation, 154(1):34-91, 1999. Google Scholar
  11. Stephan Kreutzer and Cristian Riveros. Quantitative monadic second-order logic. In LICS, pages 113-122. IEEE Computer Society, 2013. Google Scholar
  12. Daniel Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. In ICALP, pages 101-112, 1992. URL: http://dx.doi.org/10.1007/3-540-55719-9_67.
  13. Filip Mazowiecki and Cristian Riveros. Maximal Partition Logic: Towards a Logical Characterization of Copyless Cost Register Automata. In Stephan Kreutzer, editor, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015), volume 41 of Leibniz International Proceedings in Informatics (LIPIcs), pages 144-159, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2015.144.
  14. Mehryar Mohri. Finite-state transducers in language and speech processing. Computational Linguistics, 23(2):269-311, 1997. Google Scholar
  15. Christos H. Papadimitriou. Computational complexity. Addison-Wesley, 1993. Google Scholar
  16. M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM J. Res. Dev., 3(2):114-125, April 1959. URL: http://dx.doi.org/10.1147/rd.32.0114.
  17. 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