Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'487'895
Articles rated: 2609

28 March 2024
 
  » 2203360

 Article forum


Synchronizing Deterministic Push-Down Automata Can Be Really Hard
Henning Fernau ; Petra Wolf ; Tomoyuki Yamakami ;
Date 4 May 2020
AbstractThe 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 message found in this article forum.  You have a question or message about this article? Ask the community and write a message in the forum.
If you want to rate this article, please use the review section..

Subject of your forum message:
Write your forum message below (min 50, max 2000 characters)

2000 characters left.
Please, read carefully your message since you cannot modify it after submitting.

  To add a message in the forum, you need to login or register first. (free): registration page






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica