Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with regular-language
Search options not deleted
user 14207
Questions about the formal languages that can be described by regular expressions (in the sense of Kleene), or, equivalently, the languages that can be accepted by finite automata.
8
votes
Complexity of intersection of regular languages as context-free grammars
This is a great question and it really lies within my interests. I'm glad that you asked it Max.
Let $n$ DFA's with at most $O(n)$ states each be given. It would be nice if there existed a PDA with …
- 5,167
26
votes
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 …
- 5,167
4
votes
Accepted
DFSA and NFSA intersection problem
Regarding question (1):
As long as $k$ is $\Omega(n^c)$ for some $c > 0$, then the problem is $PSPACE$-complete. See this paper by Klaus-Jörn Lange and Peter Rossmanith (1992) for some related result …
- 5,167