12
votes
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
10
votes
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
8
votes
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
8
votes
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
8
votes
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
6
votes
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
5
votes
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
5
votes
Obscure characterizations of the regular languages
The following restrictions on Turing machines force them to recognize only regular languages:
space complexity $o(\log \log n)$ https://doi.org/10.1109/FOCS.1965.11
single-tape with time complexity $...
5
votes
Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?
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 ...
- 309
5
votes
Relationship between size of Boolean functions and DFAs
Complementing the other answers, here are a few research papers that explicitly study the size of (one-way) DFAs that represent Boolean functions in the way the OP describes.
Maximum and average state ...
- 6,665
5
votes
Relationship between size of Boolean functions and DFAs
Regarding question 3:
There are $S^{2S} \cdot 2^S$ different DFAs on $S$ states (fixing the initial state), and so most Boolean functions require $\Omega(2^n/n)$ states. This is the same calculation ...
- 14.5k
5
votes
Relationship between size of Boolean functions and DFAs
Here are are my attempts to answer. I'm not an expert on this subject. Please check all details for yourself.
No. Consider $f$ defined by $f(x)=1$ iff $x_1 \ne x_{n/2+1}$ or $x_2 \ne x_{n/2+2}$ or ...
- 12.3k
5
votes
Obscure characterizations of the regular languages
Here are fun ones:
computational interpretations of circular proofs for Kleene algebra in linear logic, see https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.45 (Theorem 24)
...
- 8,923
5
votes
Accepted
Deciding finiteness of regular language is NL-complete?
Let $\mathcal{A}$ be an NFA. We say that a state $q$ lies on a cycle if there is a non-empty path from $q$ to $q$ in the graph of $\mathcal{A}$. In my answer I assume that the following lemma is true:
...
- 1,347
5
votes
Can we approximate the number of words accepted by an NFA?
And now there is a faster FPRAS: https://arxiv.org/abs/2312.13320
- 111
4
votes
Obscure characterizations of the regular languages
I think this one may fit the bill:
A language is regular if and only if its characteristic series is the support of an $\mathbb{N}$-rational series.
Definitions. Let $\Sigma$ be an alphabet and $\...
- 141
3
votes
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
3
votes
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
3
votes
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
3
votes
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
3
votes
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
2
votes
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
2
votes
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
2
votes
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 ...
- 408
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.-> ...
- 11
Only top scored, non community-wiki answers of a minimum length are eligible