# Tag Info

### List of nice non-context-free languages

If I had to summarize the capabilities/limitations of CF languages I would say: they can pair "things" but two distinct pairings cannot overlap they can "count" but only linearly (...

### A split-consistency property of a formal language

We discussed your question with @M.Monet in the case of regular languages. It turns out that, unless we're mistaken, your condition is precisely equivalent to saying that the language is recognized by ...
• 9,687

### List of nice non-context-free languages

Two simple examples of non-context-free languages are PRIMES $= \{ a^p \mid p \text{ prime} \}$ and POWERS $= \{ a^{2^n} \mid n\ge 0 \}$. One can prove that they are not context-free by the pumping ...
• 4,561
Accepted

### Formalization of matching logic (logic behind K Framework)

There is a number of formalizations of matching logic in various proof assistants. I am a co-author of the first one in the following list; thus I have more insight into that one. I am not aware of ...
• 176

### 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,625

### 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

### 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
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

### 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

### 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 ...
• 4,831
Accepted

### Is there a simple characterization of regular languages closed under circular shifts?

We can propose an automaton model characterizing regular circular languages: a C-automaton is an NFA where all states are initial. A run must see an accepting state somewhere, and must start and end ...
• 8,903
Accepted

### Complexity of the inevitability problem over monoids

I think it is PSpace-complete, here is a proof scheme. We can go back to the proof scheme for PSpace-completeness of regular expression universality, e.g. described in this answer. There we can see ...
• 8,903

### 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,903

### List of nice non-context-free languages

You can group non-context-free languages into groups depending on what lemma you use to show that they are not context-free. Noam already mentioned the pumping lemma in his answer, let me mention the ...
• 14.1k

• 121

### 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

### Is there a simple characterization of regular languages closed under circular shifts?

Just an extended note trying to recover my previous (wrong) answer. A language $L$ is closed under cyclic shifts if and only if $aw \in L \Leftrightarrow wa \in L\;$ ($a \in \Sigma$) indeed after ...

### 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,625
1 vote

### List of nice non-context-free languages

The following is kind of a variant of the examples already given, but I believe it is sufficiently different that is worth mentioning. $L=\{a^n b^m a^n b^m\mid n,m\in \mathbb{N}\}$ Proof by using the ...
1 vote

### Formalization of matching logic (logic behind K Framework)

I'm currently at the end of my PhD thesis about the interoperability of semantics. That's the reason I'm studying the translation from the semantical framework K into the logical framework Dedukti. ...
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