Questions tagged [nondeterminism]
The nondeterminism tag has no usage guidance.
11
questions
27
votes
1
answer
2k
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 ...
- 9,448
31
votes
1
answer
826
views
Can graph isomorphism be decided with square root bounded nondeterminism?
Bounded nondeterminism associates a function $g(n)$ with a class $C$ of languages accepted by resource-bounded deterministic Turing machines, to form a new class $g$-$C$. This class consists of those ...
- 19k
4
votes
1
answer
317
views
minimal finite automata given in-words and out-words
this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight.
given: two finite sets of words $S_{in}$ and $S_{out}$. ...
- 11k
29
votes
2
answers
2k
views
Conditions for NFA universality
Consider a nondeterministic finite automata $A = (Q, \Sigma, \delta, q_0, F)$, and a function $f(n)$. Additionally we define $\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$.
Now lets analyze the ...
- 749
14
votes
3
answers
584
views
Nondeterministic speed-up of deterministic computation
Can nondeterminism speed-up deterministic computation? If yes, how much?
By speeding-up deterministic computation by nondeterminism I mean results of the form:
$\mathsf{DTime}(f(n)) \subseteq \...
- 21.6k
12
votes
3
answers
477
views
Does there exist a hardest DCFL?
Greibach famously defined a language $H$, the so-called nondeterministic version of $D_2$, such that any CFL is an inverse morphic image of $H$. Does there exist a similar statement with DCFL, ...
- 3,946
8
votes
1
answer
454
views
Determining if a word of specific length exists that is not accepted by a NFA
It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard?
Given an NFA and a ...
- 113
7
votes
0
answers
619
views
complexity of Sokoban with a small number of boxes
(I asked a very concise version of this one month ago on cs.stackexchange,
and although it got edited, it was not (otherwise) responded to.)
In this post, for positive integer values $k$, "$k$-...
user6973
7
votes
1
answer
348
views
Converting 2-ambiguous NFA to unambiguous NFA
This must be known, but somehow I can't locate a reference about this. Let $A$ be a nondeterministic finite automaton (NFA) over words of an alphabet $\Sigma$. I say that $A$ is unambigous if, for ...
- 9,269
6
votes
0
answers
889
views
Nondeterministic linear time vs. the deterministic time hierarchy
How much is known about nondeterministic linear time? I'm aware that $$ \mathrm{NTIME}(n) \neq \mathrm{DTIME}(n).$$
Is there an $m > 1$ so that $\mathrm{NTIME}(n) \not\subset \mathrm{DTIME}(n^m)$? ...
- 1,216
6
votes
1
answer
260
views
Is $L \subset 1NL$ when $L \neq NL$?
A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
- 119