Questions tagged [terminology]
questions about definitions, terms, and common names in theoretical computer science.
94
questions
54
votes
11
answers
5k
views
If you could rename dynamic programming...
If you could rename dynamic programming, what would you call it?
39
votes
6
answers
6k
views
Regular expressions aren't
Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton.
For ...
- 629
37
votes
2
answers
6k
views
Origins and applications of Theory A vs Theory B?
In a couple recent questions (q1 q2), there has been discussion of "Theory A" vs "Theory B", seemingly to capture the divide between the study of logic and programming languages and the study of ...
- 2,904
33
votes
1
answer
5k
views
Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming
Does someone dare to attempt to clarify what's the relation of these fields of study or perhaps even give a more concrete answer at the level of problems? Like which includes which assuming some ...
- 481
25
votes
3
answers
4k
views
What's the difference between term rewriting and pattern matching?
As there was no response at Lambda the Ultimate I try it here again: term rewriting systems are used for instance in automated theorem proving a symbolic calculation, and of course to define formal ...
- 1,259
22
votes
4
answers
1k
views
Are there problems without efficient algorithms, where existence theorems have proved such algorithms must exist?
Are there problems in CS where no efficient algorithms are known, despite existence theorems proving such efficient algorithms must exist?
What are these problems called? Where can I find out more?
- 323
17
votes
2
answers
4k
views
Is propositional resolution a complete proof system?
This question is about propositional logic and all occurrences of "resolution" should be read as "propositional resolution".
This question is something extremely basic but it has been bothering me ...
- 12.6k
17
votes
1
answer
700
views
Why are perfect graphs called perfect?
Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is ...
- 1,591
17
votes
1
answer
388
views
What is the name of this type of directed graph problem?
Take a directed graph $G$ where the edges are decorated with a a natural number. We want the set of all paths $P$ between two vertices $v_1$ and $v_2$ such that each successive edge in the path is ...
- 815
17
votes
3
answers
1k
views
Is there a name for "physical things out of which one can build a Turing machine"?
One of the amazing things about computer science is that the physical implementation is in some sense "irrelevant".
People have successfully built computers out of several different substrates -- ...
- 532
15
votes
2
answers
6k
views
What does 'gadget' mean in NP-hard reduction?
This question may not be technical. As a non-native speaker and a TA for algorithm class, I always wondered what gadget means in 'clause gadget' or 'variable gadget'. The dictionary says a gadget is a ...
15
votes
2
answers
2k
views
Why is lambda calculus a "calculus"?
The only definition of "calculus" I'm aware of is the study of limits, derivatives, integrals, etc. in analysis. In what sense is lambda calculus (or things like mu calculus) a "calculus"? How does it ...
- 269
15
votes
1
answer
2k
views
How can a problem be in NP, be NP-hard and not NP-complete?
For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP.
However, in the famous paper "The ellipsoid method and its consequences in ...
- 1,166
14
votes
1
answer
988
views
Equivalent definitions of time constructibility
We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ ...
- 532
13
votes
1
answer
1k
views
What's "pseudo time" when used in comparison with semaphores
I'm currently listening to Alan Kays' talk "Is it really complex or did we just make it complicated ?" (https://www.youtube.com/watch?v=ubaX1Smg6pY&= ) where he says that "semaphores were a bad ...
- 231
12
votes
3
answers
3k
views
what does "lifting" mean?
I see in certain places "lifting computation" or "lifting" mentioned. I haven't been able to accurately define for myself what is meant by that.
This usually comes up in computer science context. Any ...
- 131
10
votes
1
answer
472
views
Complexity of blind sort?
We all know that the minimal complexity of a comparison-based sorting algorithm is $\Omega(n \log n)$ comparisons. I'm trying to do a blind sort, i.e. given a number $n$ output a circuit (with boolean,...
user17966
10
votes
2
answers
2k
views
Maximizing sum edge weights
I am wondering if the following problem has a name, or any results related to it.
Let $G = (V,w)$ be a weighted graph where $w(u,v)$ denotes the weight of the edge between $u$ and $v$, and for all $u,...
- 9,850
9
votes
2
answers
783
views
Graph isomorphism with equivalence relation on the vertex set
A colored graph can be described as tuple $(G,c)$ where $G$ is a graph and $c : V(G) \rightarrow \mathbb{N}$ is the coloring. Two colored graphs $(G,c)$ and $(H,d)$ are said to be isomorphic if there ...
- 568
8
votes
3
answers
2k
views
Are there any intersections between Theory A and Theory B?
In the following two questions Origins and applications of Theory A vs Theory B? and Solid applications of category theory in TCS?, many people shared their knowledge and opinions about the division ...
- 181
8
votes
2
answers
1k
views
Is it right to call $2^{\sqrt{n}}$ "exponential"?
In his answer to a previous question, Sadeq Dousti recalled the following terminology:
$f(n) = n^{\omega(1)}$ is called super-polynomial. (e.g. $n^{\log n}, 2^n, 2^{2^n}$.)
$f(n) = 2^{n^{\Theta(1)}}$ ...
- 565
8
votes
2
answers
462
views
Logic Programming: Transforming B:-A C:-A to B,C:-A
I hope I've come to the right place... it's (probably) a fairly straightforward Logic Programming question.
If I have two clauses of the form:
B:-A C:-A
I can ...
- 225
8
votes
2
answers
553
views
Terminology for sparse cuts in graphs
I have found some ambiguity in how the graph parameters edge-expansion, uniform sparsest cut and conductance are defined and denoted.
My questions are: what are the definitions that best match the ...
- 4,902
7
votes
3
answers
1k
views
What is First-Order Rewritable (and FO-Query)?
I just wonder what FO Rewritable is, put an example to make it clearer for me. Also, I heard that a language that is FO Rewritable is very good, in what sense?
It is said as follow:
A class C of ...
- 223
7
votes
0
answers
165
views
A class of functions on a lattice that are easy to optimize
Let $({\cal P}(X),\subseteq)$ be the subset lattice for a finite set $X$. Consider a function $f:{\cal P}(X)\to \mathbb{R}$ with the following property: Given any element $I_0\in {\cal P}(X)$, there ...
- 201
6
votes
8
answers
1k
views
Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs
I recently came across a strange concept and was wondering if this was a known / named concept in the realm of CS.
The concept is that you evaluate some computation or logical circuit that takes in N ...
- 181
6
votes
1
answer
227
views
Typing relations terminology – how do I read typing relations?
I am currently trying to read up on type theory and have some quick questions on terminology.
In the following rule,
$$
\frac{x:T_1 \vdash t_2 : T_2}{\vdash \lambda x:T_1.t_2:T_1\to T_2}
$$
How ...
- 293
6
votes
1
answer
250
views
The "multifunction" version of ZPP?
I would like to ask if there is a name for the class of multifunctions, each of which can be computed by a probabilistic polytime Turing machine $M$ satisfying the following two conditions:
$M$ ...
- 3,664
6
votes
2
answers
536
views
(concise?) definition of thread safety
Wikipedia has the following definition:
Thread safety is a computer programming concept applicable in the
context of multi-threaded programs. A piece of code is thread-safe if
it only ...
- 251
6
votes
1
answer
155
views
Combining (block)-sensitivity and Lipschitz conditions?
If we're given a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, we can define its sensitivity as follows. The sensitivity $s(f, w)$ with respect to input $w$ is the number of ways of flipping a ...
- 32k
6
votes
1
answer
564
views
Why is combinational logic called so?
What is the significance of the word "combinational" in combinational logic?
- 63
6
votes
1
answer
280
views
Equivalent embeddings of a graph
I have difficulties finding a good definition of two embeddings of a (planar) graph in the plane being equivalent.
Intuitively I mean by equivalent that the embeddings look the same up to ...
- 63
6
votes
1
answer
242
views
Is there an accepted name for Ross Quinlan's adaptation of the ID3 decision algorithm to use a Pearson's chi-squared test for independence?
In Ross Quinlan's seminal paper Induction of Decision Trees, Quinlan summarizes the current state of machine learning in 1985 and loudly introduces the ID3 decision algorithm in the context of its ...
- 163
6
votes
0
answers
301
views
Is there a name for this property of a binary relation?
Consider a binary relation $\mathsf{R}$ such that $x\mathsf{R}y$ is the case only if there is some $z$ such that both $x\mathsf{R}z$ and $y\mathsf{R}z$ are the case.
(EDIT: note that this may be ...
- 161
6
votes
0
answers
425
views
What is the origin and meaning of the phrase "Lambda the ultimate?"
I've been messing around with functional programming languages for a few years, and I keep encountering this phrase.
I understand what lambda means, the idea of an anonymous function is both simple ...
- 263
6
votes
0
answers
220
views
What is the best fitness function for detecting natural language?
First, let me apologise, as this question is far from my area of expertise, but is related to a side interest (read hobby), and so this question might be very naive. This may even be off-topic for the ...
- 13.6k
5
votes
3
answers
1k
views
why is Linear Datalog interesting?
For those doesn't know about linear datalog, linear datalog is a datalog rule in which the number of IDB predicate in each rule is less or equal than one.
My question is, why is this interesting? ...
- 223
5
votes
1
answer
236
views
Terminology about computation and Finite algebra
I am looking for the name of something that may have one.
A finite algebra $\mathcal{A} = (E, \{f_1, f_2, \ldots, f_k\})$ is a non-empty set $E$ together with some functions $f_i$ from $E^{r_i} \to E$...
- 992
5
votes
1
answer
936
views
$O(m+n)$ really necessary for graph algorithms?
It is standard to express the running time of linear-time graph algorithms as $O(m+n)$ (such as depth-first-search, etc.).
For nearly all such algorithms, vertices of degree zero have no effect on ...
- 3,488
5
votes
1
answer
348
views
Definition of a hereditary relation
Sassone, V., Nielsen, M. and Winskel, G. (1996) Models for Concurrency: Towards a Classification. Theoretical Computer Science, 170 (1-2). pp. 297-348., p. 307:
Given a tree $S$, define … $\#$ is ...
- 557
4
votes
1
answer
533
views
Does this graph problem have a formal name?
Given an undirected weighted graph where an edge exists between every pair of nodes (n1,n2) with cost C(n1,n2), find the shortest path (possibly revisiting nodes, possibly revisiting edges) through ...
- 141
4
votes
2
answers
245
views
Can complexities differ w.r.t. different computational models?
I understand that a decision problem can be decidable with respect to certain computational models. For instance, the question whether an arbitrary sequence of parenthesis is balanced is undecidable ...
- 167
4
votes
1
answer
207
views
Minimal sum of matrix elements
Here's my attempt to explain the problem in mathematical language:
$$
\text{Given square matrix A}
$$
$$
\left(
\begin{array}{cccc}
a_{1,1} & a_{1,2} & \cdots & a_{1,N} \\
a_{2,1} ...
- 211
4
votes
1
answer
127
views
Is there a notion of "sequential" idempotence?
TL;DR: I have a definition, and I'm wondering if it already has a name or has been studied.
Suppose we have a sequence of operations (or if we want to be mathematical, functions whose domains and ...
- 141
4
votes
3
answers
297
views
Is there a name for a hashtable with a tree for each bin instead of a list?
It is well-known that the worst case performance for a chaining hashtable, is O(n), where n is the number of objects in the table. The normal assumption is that the hash is either uniform, or secure, ...
- 258
4
votes
1
answer
167
views
What is the etiquette of naming concepts after people?
There is a concept introduced by other researchers that I use in my work, and IMO it is appropriate to rename it to honor the inventors. Is it considered normal to just go ahead and name it like that ...
- 2,151
4
votes
1
answer
183
views
Need a term for a graph-theoretic/metric concept
Let $(X,d)$ be a metric space, and define $\rho$ to be the largest distance of any $x\in X$ to its nearest neighbor.
Formally,
$$ \rho = \sup_{x \in X}~ d(x, X \setminus \{x\}). $$
Does this ...
- 10.3k
4
votes
0
answers
77
views
Terminology for languages of pairs of words
I want to consider $L \subset A^* \times B^*$ as a "language". Is there standard terminology for this?
I wrote "double language" first (but that doesn't sound right to me), then &...
- 521
3
votes
1
answer
862
views
Terminology for f(g(x)) = g(f(x))
There is a paper by Ritt from 1923 that calls the relation, $f(g(x)) = g(f(x))$, permutable functions. Is there a more recent terminology used in the literature, or is this still the standard?
- 2,359
3
votes
2
answers
334
views
All literals implied by a set of horn clauses
What is the name of this problem: given a set of Horn clauses (in fact just definite clauses and facts), find the set of literals which can be deduced from it. E.g. given $\{a, a \Rightarrow b, b \...
- 1,561