|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Synchronization under Dynamic Constraints | | Petra Wolf
; | | Date: |
4 Oct 2019 | | Abstract: | Imagine an assembly line where a box with a lid and liquid in it enters in
some unknown orientation. The box should leave the line with the open lid
facing upwards with the liquid still in it. To save costs there are no complex
sensors or image recognition software available on the assembly line, so a
reset sequence needs to be computed. But how can the dependencies of the
deforming impact of a transformation of the box, such as ’do not tilt the box
over when the lid is open’ or ’open the lid again each time it gets closed’ be
modeled? We present three attempts to model constraints of these kinds on the
order in which the states of an automaton are transitioned by a synchronizing
word. The first two concepts relate the last visits of states and form
constraints on which states still need to be reached, whereas the third concept
concerns the first visits of states and forms constraints on which states might
still be reached. We examine the computational complexity of different variants
of the problem, whether an automaton can be synchronized with a word that
respects the constraints defined in the respective concept, and obtain nearly a
full classification. While most of the problems are PSPACE-complete we also
observe NP-complete variants and variants solvable in polynomial time. We will
also observe a drop of the complexity if we track the orders of states on
several paths simultaneously instead of tracking the set of active states.
Further, we give upper bounds on the length of a synchronizing word depending
on the size of the input relation and show that the Cerny conjecture holds for
partial weakly acyclic automata. | | Source: | arXiv, 1910.1935 | | 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