# Tag Info

### Automata reaching the same state when reading the same word long enough

Adding to Mikhail Rudoy's very good answer: the languages of the form $\Sigma^*\cdot X \cup Y$ are known under the name definite languages (resp. definite events in the lingo of the 1960s). The ...
• 6,625
1 vote

### Automata reaching the same state when reading the same word long enough

Such an automaton is called kâ€“determined. It is very closely related to foldings of de Bruijn graphs.
• 111

### Can we decide the existence of some regular language closed under a Thue system?

The problem is undecidable, already for very particular cases. This is because in the case $\Sigma'=\Sigma$, the problem is equivalent to deciding whethe r a given rational subset of a monoid $M$ is ...
Accepted

### Automata reaching the same state when reading the same word long enough

I don't have any references to point you towards for this kind of automaton, but I can tell you exactly what languages can be recognized by this type of automaton. An automaton of this form must ...
• 2,873

### Automata reaching the same state when reading the same word long enough

This is very reminiscent of synchronizing words. However in your case all words of length more than $k$ are synchronizing.
• 371
1 vote

### Automata reaching the same state when reading the same word long enough

Edit: following an edit to the question, what follows is not correct -- it assumes that the state reached is the same for all words. I think that the automata that obey your condition recognize ...
• 9,687
No. Consider the problem $L=\{(n,x) ; x_n = 1 \}$ (where $n$ is a number written in binary). This is solvable in $O(\log(n))$ by a RAM machine but it takes at least $O(n)$ to be solved by a Turing ...
I doubt it, but I have no proof. Consider the following problem: Input: A permutation $\sigma$ of $\{1,2,\dots,n\}$, represented as the list $(\sigma(1),\sigma(2),\dots,\sigma(n))$ (i.e., one-line ...