# Questions tagged [terminology]

Questions about how specific notions have to be understood as well as conventions of notation.

1,076 questions
Filter by
Sorted by
Tagged with
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} ...
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 (...
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$ ...
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 ...
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, ...
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 ...
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 ...
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 ...