| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Synchronization of Deterministic Visibly Push-Down Automata | Henning Fernau
; Petra Wolf
; | Date: |
5 May 2020 | Abstract: | We generalize the concept of synchronizing words for finite automata, which
map all states of the automata to the same state, to deterministic visibly
push-down automata. Here, a synchronizing word w does not only map all states
to the same state but also fulfills some conditions on the stack content of
each run after reading w. We consider three types of these stack constraints:
after reading w, the stack (1) is empty in each run, (2) contains the same
sequence of stack symbols in each run, or (3) contains an arbitrary sequence
which is independent of the other runs. We show that in contrast to general
deterministic push-down automata, it is decidable for deterministic visibly
push-down automata whether there exists a synchronizing word with each of these
stack constraints, i.e., the problems are in EXPTIME. Under the constraint (1)
the problem is even in P. For the sub-classes of deterministic very visibly
push-down automata the problem is in P for all three types of constraints. We
further study variants of the synchronization problem where the number of turns
in the stack height behavior caused by a synchronizing word is restricted, as
well as the problem of synchronizing a variant of a sequential transducer,
which shows some visibly behavior, by a word that synchronizes the states and
produces the same output on all runs. | Source: | arXiv, 2005.1374 | 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 claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |