One deterministic-counter automata

We introduce one deterministic-counter automata (ODCA), which are one-counterautomata where all runs labelled by a given word have the same counter effect, a property we call counter-determinacy. ODCAs are an extension of visiblyone-counter automata - one-counter automata (OCA), where the input alphabetdetermines the actions on the counter. They are a natural way to introducenon-determinism/weights to OCAs while maintaining the decidability of crucialproblems that are undecidable on general OCAs. For example, the equivalenceproblem is decidable for deterministic OCAs, whereas it is undecidable fornon-deterministic OCAs. We consider both non-deterministic and weighted ODCAs. Our work shows that the equivalence problem is decidable in polynomial timefor weighted ODCAs over a field and polynomial space for non-deterministicODCAs. As a corollary, we get that the regularity problem, i. e. , the problem ofchecking whether an input weighted ODCA is equivalent to some weightedautomaton, is also in polynomial time. Furthermore, we show that the coveringand coverable equivalence problems for uninitialised weighted ODCAs aredecidable in polynomial time. We also introduce a few reachability problemsthat are of independent interest and show that they are in P. Thesereachability problems later help in solving the equivalence problem. https: //arxiv. org/abs/2301. 13456 Contributed talk given by Prince Mathew

Authors

• Prince Mathew

Keywords

No keywords are indexed for this paper.