|
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
|
|
|
ISSN
|
|
|
|
0302-9743
[print]
1611-3349
[online]
|
|
|
ISBN
|
|
|
|
978-3-319-98653-1
978-3-319-98654-8
|
|
|
DOI
|
|
|
|
10.1007/978-3-319-98654-8_7
|
|
|
Volume/pages
|
|
|
|
11088
(2018)
, p. 83-95
|
|
|
Full text (Publisher's DOI)
|
|
|
|
|
|
|
Full text (open access)
|
|
|
|
|
|