|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'502'364
Articles rated: 2609
23 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Synchronizing Deterministic Push-Down Automata Can Be Really Hard | | Henning Fernau
; Petra Wolf
; Tomoyuki Yamakami
; | | Date: |
4 May 2020 | | Abstract: | The question if a deterministic finite automaton admits a software reset in
the form of a so-called synchronizing word can be answered in polynomial time.
In this paper, we extend this algorithmic question to deterministic automata
beyond finite automata. We prove that the question of synchronizability becomes
undecidable even when looking at deterministic one-counter automata. This is
also true for another classical mild extension of regularity, namely that of
deterministic one-turn push-down automata. However, when we combine both
restrictions, we arrive at scenarios with a PSPACE-complete (and hence
decidable) synchronizability problem. Likewise, we arrive at a decidable
synchronizability problem for (partially) blind deterministic counter automata.
There are several interpretations of what synchronizability should mean for
deterministic 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 it
arbitrary? For the automata classes studied in this paper, the complexity or
decidability status of the synchronizability problem is mostly independent of
this technicality, but we also discuss one class of automata where this makes a
difference. | | Source: | arXiv, 2005.1381 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER