Universality and Forall-Exactness of Cost Register Automata with Few Registers

Daviaud, Laure and Ryzhikov, Andrew (2023) Universality and Forall-Exactness of Cost Register Automata with Few Registers. In: 48th International Symposium on Mathematical Foundations of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs). (In Press)

[thumbnail of accepted manuscript]
PDF (accepted manuscript) - Accepted Version
Download (423kB) | Preview


The universality problem asks whether a given finite state automaton accepts all the input words. For quantitative models of automata, where input words are mapped to real values, this is naturally extended to ask whether all the words are mapped to values above (or below) a given threshold. This is known to be undecidable for commonly studied examples such as weighted automata over the positive rational (plus-times) or the integer tropical (min-plus) semirings, or equivalently cost register automata (CRAs) over these semirings. In this paper, we prove that when restricted to CRAs with only three registers, the universality problem is still undecidable, even with additional restrictions for the CRAs to be copyless linear with resets. In contrast, we show that, assuming the unary encoding of updates, the ForAll-exact problem (does the CRA output zero on all the words?) for integer min-plus linear CRAs can be decided in polynomial time if the number of registers is constant. Without the restriction on the number of registers this problem is known to be PSPACE-complete.

Item Type: Book Section
Uncontrolled Keywords: 3*,possibly 4* ,/dk/atira/pure/researchoutput/REFrank/3_
Faculty \ School: Faculty of Science > School of Computing Sciences
Depositing User: LivePure Connector
Date Deposited: 01 Aug 2023 08:30
Last Modified: 01 Aug 2023 08:30
URI: https://ueaeprints.uea.ac.uk/id/eprint/92739

Actions (login required)

View Item View Item