# Tag Info

Accepted

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

Simple answer: If there does exist a more efficient algorithm that runs in $O(n^{\delta})$ time for some $\delta < 2$, then the strong exponential time hypothesis would be refuted. We will prove a ...
• 4,900

### Automata learning without counterexamples

Consider password automata: for each $w\in\{0,1\}^n$, the DFA $M_w$ accepts the language $\{w\}$. In this case, a membership query is the same as an equivalence query --- and clearly, you'll need ...
• 10k
Accepted

• 4,721

### Regular versus TC0

Regular languages with unsolvable syntactic monoids are $\mathrm{NC}^1$-complete (due to Barrington; this is the underlying reason behind the more commonly quoted result that $\mathrm{NC}^1$ equals ...
• 14.8k
Accepted

### Parameterized complexity of inclusion of regular languages

The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even ...
• 7,653

• 3,816

### On the realisation of monoids as syntactic monoids of languages

The terminology rigid seems to be relatively new compared to the term disjunctive used in the late 70's (and probably before, I didn't check for earlier references). A subset $P$ of a monoid $M$ is ...
• 4,721

• 4,721