Directable and Synchronizable Parikh Automata

A finite and deterministic complete automaton is \emph{synchronizing} if there exists a reset state and an input word that drives the automaton to the reset state when started from any state. The notion of synchronizability has been extended to various other models: non-deterministic and partial automata, weighted and timed automata, register automata, nested word automata, Markov decision processes, probabilistic automata and push-down automata. Parikh automata were introduced by Klaedtke & Rueß and enrich finite automata with counters that are checked against a semilinear condition at the end. Here, we will present various notions of synchronization for Parikh automata that yield decidable problems that are PSPACE-complete in general. We will also consider subclasses for which the problem is NP-complete or polynomial time computable. This is ongoing (yet unpublished) work.

Authors

• Stefan Hoffmann

Keywords

No keywords are indexed for this paper.