Weak Cost Register Automata are Still Powerful

DOI10.1142/S0129054120410026zbMath1458.68080OpenAlexW3099018049MaRDI QIDQ5859644

Guillermo A. Pérez, Michaël Cadilhac, Filip Mazowiecki, Shaull Almagor

Publication date: 19 April 2021

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054120410026

zbMATH Keywords

equivalencesemilinearitycost register automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Limitedness theorem on finite automata with distance functions
• On the degree of ambiguity of finite automata
• A theory of timed automata
• Finite-memory automata
• Expressiveness of Streaming String Transducers
• What’s Decidable about Weighted Automata?
• Sequences of Level 1, 2, 3,..., k,...
• Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties
• Regular Functions and Cost Register Automata
• Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata
• UNAMBIGUOUS CONSTRAINED AUTOMATA

This page was built for publication: Weak Cost Register Automata are Still Powerful