# Tag Info

### Obscure characterizations of the regular languages

I know it is frowned upon to promote one's own results, but it turns out that I wrote an article precisely on this topic. So let me add a few characterizations of regular languages not already ...
• 5,101
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,883
Accepted

### The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states

As observed in the proof of Theorem 6 (later dubbed the "Star Height Lemma") of Gruber/Holzer ICALP 2008, when converting a regular expression into an $\varepsilon$-NFA, then the underlying ...
• 6,665
Accepted

### Error in Robson's proof about separating strings?

Converting my comment to an answer: This is taken care of in the paragraph just before Theorem 1. If the accepting state is reached at some $v_j$, then we necessarily have $j>i$, and we can compose ...
• 881

### 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,665
Accepted

### Intersection Non-Emptiness for Two-Way Finite Automata

Unlike one-way models, intersection of 2-way NFAs is "cheap": Given 2-way NFAs $A_1,A_2$, you can construct a 2-way NFA $B$ for their intersection that works as follows: it first behaves ...
• 5,616

### The empty tree-word for regular tree languages

I believe this is one of the many cases where it becomes clear that labelling nodes is a bad choice, and we should be labelling edges instead. In the edge-labelled framework, the empty tree is simply ...
• 8,923

• 141

### Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?

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 ...
• 12.3k

### 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.
• 309
Accepted

### Modify DCFG to enforce length limit

A partial answer: The number of productions needed by a (not necessarily deterministic) context-free grammar generating $L\cap \Sigma^{\le N}$ in the worst case is $\Theta(N^2)$, as given in Theorem 4 ...
• 6,665

### Obscure characterizations of the regular languages

A language is regular if and only if it is linearly separable by the DFA kernel, defined here: How many DFAs accept two given strings? This is Theorem 11 in https://www.sciencedirect.com/science/...
• 10.6k

### What is the importance of linear languages?

Adding to the existing answer, the restriction to linear grammars also inspired similar restrictions in classical, and other grammatical models. To name a few: metalinear grammars, that is, context-...
• 6,665
Accepted

### Are regular expressions polynomially decomposable?

The answer to my question turned out to be positive, which follows from a translation from regular expressions to automata and back. Check the answer of Hermann Gruber to my previous POST.
• 1,347

### Is it useful to "untangle" an NFA by converting to a regular expression and back

In fact, this roundtrip conversion is used in the proof of the Star Height Lemma, and this in turn has lots of implications in the area of descriptional complexity of regular expressions. And here it ...
• 6,665
Accepted

### What is the current state of the art on exact identification of DFAs with a maximum N states

The last step of the proposed reasoning can be done as described in https://cs.stackexchange.com/questions/48136/testing-two-dfas-generate-the-same-language-by-trying-all-strings-upto-a-certain and in ...
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
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,707
1 vote

### What is the intution on the TTT algorithm for regular grammar inference?

If you get a counterexample back from the teacher the counterexample is very long. If the suffix analysis is used as described in the paper, the suffix can be very long, this suffix is added in the ...
1 vote
Accepted

### Counting the different subsets of nodes seen when iterating a subset through a directed graph

The argument in Chrobak’s paper can be applied to this problem as well, with the same bounds. Let $\{D_i:i<k\}$ be the set of strongly connected components of $G$ that contain a cycle (i.e., other ...
• 18.2k
1 vote

### Equivalence between GNFA and NFA/DFA

You agree that every GNFA has a corresponding regular expression. Then we know that each regular expression has a corresponding DFA, and an NFA. Thus we can follow the path of GNFA-> reg. exp.-> ...

Only top scored, non community-wiki answers of a minimum length are eligible