Book section

### Reachability in Succinct and Parametric One-Counter Automata

Abstract:

One-counter automata are a fundamental and widely-studied class of infinite-state systems. In this paper we consider one-counter automata with counter updates encoded in binary-which we refer to as the succinct encoding. It is easily seen that the reachability problem for this class of machines is in PSpace and is NP-hard. One of the main results of this paper is to show that this problem is in fact in NP, and is thus NP-complete. We also consider parametric one-counter automata, in which cou...

Publication status:
Published

### Authors

More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Volume:
5710
Pages:
369-383
Publication date:
2009-01-01
DOI:
URN:
Source identifiers:
296467
Local pid:
pubs:296467
ISBN:
978-3-642-04080-1