Conference item icon

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:
Publisher copy:
10.1109/LICS.2017.8005101

Authors


More by this author
Institution:
University of Oxford
Oxford college:
University College
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Funding agency for:
Benedikt, M
Grant:
EP/M005852/1, EP/N014359/1, EP/L012138/1
More from this funder
Funding agency for:
Worrell, J
Grant:
EP/M012298/1
Publisher:
IEEE Publisher's website
Journal:
Proceedings - Symposium on Logic in Computer Science Journal website
Host title:
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Publication date:
2017-08-18
Acceptance date:
2017-03-01
DOI:
ISSN:
1043-6871
Source identifiers:
695693
ISBN:
9781509030187
Pubs id:
pubs:695693
UUID:
uuid:f341421b-2130-42d7-bb21-52442bad0b80
Local pid:
pubs:695693
Deposit date:
2017-05-18

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP