Conference item
Weak cost register automata are still powerful
- Abstract:
- We consider one of the weakest variants of cost register automata over a tropical semiring, namely copyless cost register automata over N with updates using min and increments. We show that this model can simulate, in some sense, 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 simulated by a restricted form of linearly-ambiguous weighted automata.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 539.4KB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-319-98654-8_7
Authors
- Publisher:
- Springer
- Host title:
- 22nd International Conference on Developments in Language Theory (DLT 2018)
- Journal:
- 22nd International Conference on Developments in Language Theory (DLT 2018) More from this journal
- Publication date:
- 2018-08-05
- Acceptance date:
- 2018-06-09
- DOI:
- Pubs id:
-
pubs:912165
- UUID:
-
uuid:95aba65d-9ab1-412a-bf06-36bbba4b0e7e
- Local pid:
-
pubs:912165
- Source identifiers:
-
912165
- Deposit date:
-
2018-09-06
Terms of use
- Copyright holder:
- Springer Nature Switzerland
- Copyright date:
- 2018
- Notes:
- © Springer Nature Switzerland AG 2018. This is the accepted manuscript version of the article. The final version is available online from Springer at: https://doi.org/10.1007/978-3-319-98654-8_7
If you are the owner of this record, you can report an update to it here: Report update to this record