English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The question if a deterministic finite automaton admits a software reset inthe form of a so-called synchronizing word can be answered in polynomial time.In this paper, we extend this algorithmic question to deterministic automatabeyond finite automata. We prove that the question of synchronizability becomesundecidable even when looking at deterministic one-counter automata. This isalso true for another classical mild extension of regularity, namely that ofdeterministic one-turn push-down automata. However, when we combine bothrestrictions, we arrive at scenarios with a PSPACE-complete (and hencedecidable) synchronizability problem. Likewise, we arrive at a decidablesynchronizability problem for (partially) blind deterministic counter automata.  There are several interpretations of what synchronizability should mean fordeterministic push-down automata. This is depending on the role of the stack:should it be empty on synchronization, should it be always the same or is itarbitrary? For the automata classes studied in this paper, the complexity ordecidability status of the synchronizability problem is mostly independent ofthis technicality, but we also discuss one class of automata where this makes adifference.

Synchronizing Deterministic Push-Down Automata Can Be Really Hard