Book section icon

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...

Expand abstract
Publication status:
Published

Actions


Access Document


Authors


Kreutzer, S More by this author
Ouaknine, J More by this author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Volume:
5710
Pages:
369-383
Publication date:
2009
DOI:
URN:
uuid:18ad460c-18d3-482b-bb90-393904c57087
Source identifiers:
296467
Local pid:
pubs:296467
ISBN:
978-3-642-04080-1

Terms of use


Metrics



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

TO TOP