Conference item
Polynomial automata: zeroness and applications
- Abstract:
- We introduce a generalisation of weighted automata over a field, called polynomial automata, and we analyse the complexity of the Zeroness Problem in this model, that is, whether a given automaton outputs zero on all words. While this problem is non-primitive recursive in general, we highlight a subclass of polynomial automata for which the Zeroness Problem is primitive recursive. Refining further, we identify a subclass of affine VAS for which coverability is in 2EXPSPACE. We also use polynomial automata to obtain new proofs that equivalence of streaming string transducers is decidable, and that equivalence of copyless streaming string transducers is in PSPACE.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 359.6KB, Terms of use)
-
- Publisher copy:
- 10.1109/LICS.2017.8005101
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Funding agency for:
- Benedikt, M
- Worrell, J
- Grant:
- EP/M005852/1, EP/N014359/1, EP/L012138/1
- EP/M012298/1
- Publisher:
- IEEE
- Host title:
- 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- Journal:
- Proceedings - Symposium on Logic in Computer Science More from this journal
- Publication date:
- 2017-08-18
- Acceptance date:
- 2017-03-01
- DOI:
- ISSN:
-
1043-6871
- ISBN:
- 9781509030187
- Pubs id:
-
pubs:695693
- UUID:
-
uuid:f341421b-2130-42d7-bb21-52442bad0b80
- Local pid:
-
pubs:695693
- Source identifiers:
-
695693
- Deposit date:
-
2017-05-18
- ARK identifier:
Terms of use
- Copyright holder:
- IEEE
- Copyright date:
- 2017
- Notes:
- Copyright © 2017 IEEE. This is the accepted manuscript version of the article. The final version is available online from IEEE at: https://doi.org/10.1109/LICS.2017.8005101
If you are the owner of this record, you can report an update to it here: Report update to this record