Back to Search
Start Over
Continuous One-counter Automata.
- Source :
- ACM Transactions on Computational Logic; Jan2023, Vol. 24 Issue 1, p1-31, 31p
- Publication Year :
- 2023
-
Abstract
- We study the reachability problem for continuous one-counter automata, COCA for short. In such automata, transitions are guarded by upper- and lower-bound tests against the counter value. Additionally, the counter updates associated with taking transitions can be (non-deterministically) scaled down by a nonzero factor between zero and one. Our three main results are as follows: we prove (1) that the reachability problem for COCA with global upper- and lower-bound tests is in NC²; (2) that, in general, the problem is decidable in polynomial time; and (3) that it is NP-complete for COCA with parametric counter updates and bound tests. [ABSTRACT FROM AUTHOR]
- Subjects :
- POLYNOMIAL time algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 15293785
- Volume :
- 24
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- ACM Transactions on Computational Logic
- Publication Type :
- Academic Journal
- Accession number :
- 161456629
- Full Text :
- https://doi.org/10.1145/3558549