Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
1,076
questions
0
votes
3answers
246 views
Transform regular grammar in linear grammar
My problem is how can I transform a regular grammar into a linear grammar?
I know that a linear grammar has the form
$\begin{align} A &\to w_1Bw_2 \\
A &\to w \end{align}$
...
6
votes
1answer
2k views
Space bounded Turing Machine - clarification on Computational Complexity (book: Arora-Barak ) question 4.1
I have the following question from Computational Complexity - A modern Approach by Sanjeev Arora and Boaz Barak:
[Q 4.1]
Prove the existence of a universal TM for space bounded computation (...
4
votes
1answer
137 views
Need help understanding this optimization problem on graphs
Has anyone seen this problem before? It's suppose to be NP-complete.
We are given vertices $V_1,\dots ,V_n$ and possible parent sets for each vertex. Each parent set has an associated cost. Let $O$ ...
3
votes
2answers
185 views
What does this performance formula mean?
I have to make a quick clustering program but the following formula is gibberish to me:
$\operatorname{Perf}(X,C) = \sum\limits_{i=1}^n\min\{||X_i-C_l||^2 \mid l = 1,...,K\}$
where $X$ is a ...
6
votes
1answer
189 views
Probabilistic poly-time machine always halts on all inputs?
In the usual definition of probabilistic poly-time machine it is said that the machine halts in polynomial time for all inputs.
Is the intention really to say that the machine halts for all inputs, ...
12
votes
1answer
558 views
What is complexity class $\oplus P^{\oplus P}$
What does the complexity class $\oplus P^{\oplus P}$ mean? I know that $\oplus P$ is the complexity class which contains languages $A$ for which there is a polynomial time nondeterministic Turing ...
31
votes
2answers
3k views
Why is a regular language called 'regular'?
I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata.
He defines a regular language as anything ...
4
votes
2answers
683 views
Big-Endian/Little-Endian argument - paper by Danny Cohen
Reading a book I was redirected to "On holy wars and a plea for peace" paper by Danny Cohen, which covers the "holy war" between big-endians and little-endians considering byte-order.
Reaching the ...
63
votes
7answers
70k views
Distributed vs parallel computing
I often hear people talking about parallel computing and distributed computing, but I'm under the impression that there is no clear boundary between the 2, and people tend to confuse that pretty ...
16
votes
2answers
1k views
Scott-continuous functions: an alternative definition
I'm really struggling with this property:
Let $X,Y$ be coherence spaces and $f: Cl(X) \rightarrow Cl(Y)$ be a monotone function. $f$ is continuous if and only if $f(\bigcup_{x\in D} x)=\bigcup_{x \in ...
5
votes
2answers
327 views
What is co-something?
What does the notation co- mean when prefixing co-NP, co-RE (recursively enumerable), or <...
9
votes
3answers
10k views
Cross Compiler's T diagram
I'm studying Bootstrapping from Red Dragon Book Compilers and found the T diagram for cross compiler pretty confusing. I can't understand what is meant by "Run compiler1 through compiler2". Can anyone ...
24
votes
5answers
15k views
What is meant by "solvable by non deterministic algorithm in polynomial time" [duplicate]
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 deterministic ...
16
votes
2answers
2k views
What is the difference between "Decision" and "Verification" in complexity theory?
In Michael Sipser's Theory of Computation on page 270 he writes:
P = the class of languages for which membership can be decided quickly.
NP = the class of languages for which membership can be ...
6
votes
2answers
9k views
Which queue does the long-term scheduler maintain?
There are different queues of processes (in an operating system):
Job Queue: Each new process goes into the job queue. Processes in the job queue reside on mass storage and await the allocation of ...
33
votes
2answers
44k views
What is the difference between user-level threads and kernel-level threads?
After reading several sources I'm still confused about user- and kernel-level threads.
In particular:
Threads can exist at both the user level and the kernel level
What is the difference between ...
29
votes
5answers
10k views
"NP-complete" optimization problems
I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. ...
17
votes
3answers
458 views
Difference between "information" and "useful information" in algorithmic information theory
According to Wikipedia:
Informally, from the point of view of algorithmic information theory, the information content of a string is equivalent to the length of the shortest possible self-contained ...
11
votes
1answer
3k views
How does Stack Inspection work?
This is precursor to my other, more advanced question about Stack Inspection.
Stack Inspection is a security mechanism introduced in the JVM to deal with running code originating from locations ...
7
votes
2answers
388 views
Are two elements always in a relation within a partially ordered set?
In a partially ordered set, am I always able to order two arbitrary elements out of the set? Or is it possible that two elements within the set have no order relation to each other?
For example if ...
23
votes
2answers
3k views
What is beta equivalence?
In the script I am currently reading on the lambda calculus, beta equivalence is defined as this:
The $\beta$-equivalence $\equiv_\beta$ is the smallest equivalence that contains $\rightarrow_\beta$...
75
votes
2answers
9k views
What is coinduction?
I've heard of (structural) induction. It allows you to build up finite structures from smaller ones and gives you proof principles for reasoning about such structures. The idea is clear enough.
But ...
4
votes
2answers
4k views
What is the height of an empty BST when using it in context for balancing?
Suppose the datatype for a BST is defined as follows (in SML)
datatype 'a bst_Tree =
Empty
| Node of (int * 'a) * 'a bst_Tree * 'a bst_Tree;
So there are two ...
51
votes
4answers
7k views
Why polynomial time is called "efficient"?
Why in computer science any complexity which is at most polynomial is considered efficient?
For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms ...
8
votes
1answer
315 views
The essential difference between spiking neural networks and earlier generation ANN's
I have been studying Spiking Neural Networks online from various papers, mainly Maass (1997). I am not entirely sure I understand what makes SNN's pulse-code in contrast to earlier ANNs which are ...
96
votes
3answers
30k views
How does one know which notation of time complexity analysis to use?
In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity.
However, there are ...
