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 polyno...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Accepted manuscript, pdf, 359.6KB)
-
- Publisher copy:
- 10.1109/LICS.2017.8005101
Authors
Funding
+ 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
Bibliographic Details
- Publisher:
- IEEE Publisher's website
- Host title:
- 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- Journal:
- Proceedings - Symposium on Logic in Computer Science Journal website
- Publication date:
- 2017-08-18
- Acceptance date:
- 2017-03-01
- DOI:
- ISSN:
-
1043-6871
- ISBN:
- 9781509030187
Item Description
- Pubs id:
-
pubs:695693
- UUID:
-
uuid:f341421b-2130-42d7-bb21-52442bad0b80
- Local pid:
- pubs:695693
- Source identifiers:
-
695693
- Deposit date:
- 2017-05-18
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
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record