# Questions tagged [automata-theory]

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

53 questions
Filter by
Sorted by
Tagged with
1k views

### Deciding emptiness of intersection of regular languages in subquadratic time

Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input. Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which ...
704 views

304 views

### Name this digraph

I am trying to track down the name of this digraph and some references: You take all members of the transformation semigroup on $n$ elements, $T_{n}$. For two members $x$ ,$y$ ; if $x$ is in the ...
233 views

### Automata and a kind of pumping lemma on state transition function

We encountered this question as an exercise in a Büchi automata book a couple of decades ago, and back then gave a few tries thinking that it should be easy. But haven't seen a solution. My ...
301 views

### Inductive definition of ECTL*: how are recursive formulas forbidden?

In [1], the extended computation tree logic ECTL* is inductively defined as the propositional formulas over all E($A(F_1,..F_n)$), where E is the existential path quantifier and $A$ some Büchi ...
872 views

### The class CFL\cap co-CFL

Is anything nontrivial known about the class $\mathrm{CFL}\cap \mathrm{coCFL}$? In particular, is it known whether $\mathrm{CFL}\cap \mathrm{coCFL} = \mathrm{DCFL}$ (certainly the reverse containment ...
170 views

### Getting an automaton from set of words in and out of a language [duplicate]

Possible Duplicate: Is finding the minimum regular expression an NP-complete problem? Let's suppose that I have an unknown language $\mathcal L$, I know only two (particularly large) sets of ...
Are locally testable languages closed under complementation? I guess yes, because when I can decide membership by sliding a window of size $k$ over the word and looking if the $k$-length words ...