The nondeterminism tag has no wiki summary.
1
vote
1answer
60 views
Converting an NFA to regex using GNFA algorithm?
So I've been trying to crack this for a long time and almost feel like I am going in loops about this question.
Given the following NFA:
Using the GNFA algorithm get the regular expression.
I ...
2
votes
0answers
25 views
Classes of NFAs which allow efficient subset testing or unambiguity conversions
I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete.
I'm wondering, ...
1
vote
2answers
53 views
Unsure on how to create a NFA for this language
Basically, I currently have two ideas but unsure on which is correct for the following question:
"The High level data link control protocol (HDLC), is a popular protocol used for point-to-point data ...
1
vote
1answer
49 views
what is glushkov NFA. What is the difference between Glushkov NFA and Thompson NFA?
I saw this term "Glushkov NFA" at http://lambda-the-ultimate.org/node/2064 . Search engines are returning references to articles that use glushkov nfa, but nothing specific about the glushkov nfa ...
6
votes
2answers
63 views
Why is one often requiring space constructibility in Savitch's theorem?
When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I ...
1
vote
1answer
82 views
Closure of regular Language - Transition Function : Sipser Proof
I was going through construction proofs for closure of regular languages under union, star and concatenation operation in the book: "Introduction to Theory of Computation" by Michael Sipser.
I have ...
3
votes
2answers
88 views
Equivalence of NFA and DFA - proof by construction
I was looking at the construction proof showing the equivalence of NFA and DFA from Sipser's text. It started by taking number of states of DFA as $\mathcal{P}(Q)$, where $\mathcal{P}(Q)$ is the set ...
3
votes
4answers
124 views
Are there real lexers that use NFAs directly instead of first transforming them to DFAs?
I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic ...
1
vote
1answer
74 views
Non-deterministic Turing machine that halts on at least one branches of computation
I'm looking at my textbook here from Michael Sipser and he says that a nondeterministic Turing machine is a decider if all its computation branches halt on all inputs. I think I recall seeing ...
7
votes
6answers
295 views
Can we say DFA is more efficient than NFA?
I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it ...
2
votes
1answer
67 views
Non-deterministic algorithm for solving figure of 8
I am struggling in trying to figure out a non-deterministic algorithm for the following problem.
Consider the following problem, called the figure-of-eight problem (FOE). An instance is an undirected ...
4
votes
1answer
95 views
What is prefix monotonicity?
I have a background in computer architecture and only cursory understanding of process networks. For a paper I am writing I need to understand prefix monotonicity properly.
For now I have "a stream ...
4
votes
1answer
84 views
What is the state of the art in encapsulated search in functional logic programming?
I am particularly interested in solutions to the problem that encapsulated search can depend on the order of evaluation.
According to [1], encapsulated search in PAKCS depends on the order of ...
2
votes
0answers
58 views
Logarithmic space difference between deterministic and non-deterministic algorithms
I had an interview today, and the interviewer has told me about a theorem (of someone called Hill- or Hell-something) which states that for a non-deterministic algorithm there exists a deterministic ...
1
vote
1answer
49 views
Are any problems in P known to have logarithmic-time-verifiable certificates?
Problems in NP have certificates which can be verified in polynomial time.
It seems conceivable that there could be problems in P which have certificates which can be verified in logarithmic time. ...
1
vote
0answers
80 views
Proving that no deterministic algorithm can be better than a 3-approximation
There are three popular beach resorts, A, B, and C, which reside on a line:
A-----(1km)-----B-----(1km)------C.
The distances between the ...
1
vote
1answer
80 views
How does this non-deterministic algorithm to find if a Hamiltonian path exists work?
I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$:
Write a ...
1
vote
1answer
78 views
Visualizing a Non Deterministic Decider
I know that we can visualize a Non deterministic TM as a TM which splits into multiple copies of itself whenever it sees a non deterministic path (Yes, I also know that this is just a visualization ...
8
votes
1answer
111 views
Classfication of randomized algorithms
From Wikipedia about randomized algorithms
One has to distinguish between algorithms that use the random
input to reduce the expected running time or memory usage, but always
terminate with a ...
2
votes
1answer
68 views
Superpolynomial time set such that SP=NSP is known?
Are there any superpolynomial time set $\mathsf{SP}$ in between $\mathsf{P}$ and $\mathsf{EXPTIME}$ such that the problem $\mathsf{SP}=\mathsf{NSP}$ has a known answer?
UPDATE: It must be defined by ...
10
votes
4answers
1k views
Differences and relations between randomized and nondeterministic algorithms?
What differences and relations are between randomized algorithms and nondeterministic algorithms?
From Wikipedia
A randomized algorithm is an algorithm which employs a degree of
randomness as ...
7
votes
3answers
92 views
How to prove that DFAs from NFAs can have exponential number of states?
All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. ...
3
votes
3answers
146 views
Length of the certificate in complexity classes
A nondeterministic machine trying to decide membership in a language
is presented with a hint (called a "witness" or "certificate") which
proves membership (no such witness is provided for ...
4
votes
3answers
110 views
Why does NTIME consider the length of the longest computation?
In Sipser's textbook "Introduction to the Theory of Computation, Second Edition," he defines nondeterministic time complexity as follows:
Let $N$ be a nondeterministic Turing machine that is a ...
8
votes
2answers
295 views
What is the difference between quantum TM and nondetermistic TM?
I was going through the discussion on the question How to define quantum-turing-machines? and I feel that quantum TM and nondetermistic TM are one and the same. The answers to the other question do ...
6
votes
4answers
405 views
Words that have the same right- and left-associative product
I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting:
Give a non deterministic finite automaton accepting ...
8
votes
4answers
368 views
What is meant by “solvable by non deterministic algorithm in polynomial time”
In many textbooks NP problems are defined as:
Set of all decision problems solvable by non deterministic algorithms in polynomial time
I couldn't understand the part "solvable by non ...
10
votes
1answer
506 views
Computational power of deterministic versus nondeterministic min-heap automata
This is a follow-up question of this one.
In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
14
votes
3answers
389 views
What are the conditions for a NFA for its equivalent DFA to be maximal in size?
We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in ...
