Publication
Title
Weak cost register automata are still powerful
Author
Abstract
We consider one of the weakest variants of cost register automata over a tropical semiring, namely copyless cost register automata over Open image in new window with updates using min and increments. We show that this model can simulate, in some sense, the runs of counter machines with zero-tests. We deduce that a number of problems pertaining to that model are undecidable, in particular equivalence, disproving a conjecture of Alur et al. from 2012. To emphasize how weak these machines are, we also show that they can be expressed as a restricted form of linearly-ambiguous weighted automata.
Language
English
Source (journal)
Lecture notes in computer science. - Berlin, 1973, currens
Source (book)
22nd International Conference, DLT 2018, September 10-14, 2018, Tokyo, Japan / Hoshi, Mizuho [edit.]; et al.
Source (series)
Theoretical computer science and general issues (LNTCS) ; 11088
Publication
Cham : Springer , 2018
ISBN
978-3-319-98653-1
978-3-319-98654-8
Volume/pages
11088 (2018) , p. 83-95
Full text (Publisher's DOI)
Full text (open access)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
External links
Record
Identification
Creation 19.11.2018
Last edited 12.10.2020