Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Questions tagged [terminology]

questions about definitions, terms, and common names in theoretical computer science.

Filter by
Sorted by
Tagged with
52 votes
11 answers
4k views

If you could rename dynamic programming...

If you could rename dynamic programming, what would you call it?
40 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 ...
user avatar
34 votes
2 answers
4k 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 ...
user avatar
  • 2,864
32 votes
1 answer
4k 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 ...
user avatar
  • 471
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 ...
user avatar
  • 1,249
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?
user avatar
  • 323
17 votes
1 answer
658 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 ...
user avatar
  • 1,571
17 votes
1 answer
386 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 ...
user avatar
  • 805
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 -- ...
user avatar
15 votes
2 answers
5k 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 ...
user avatar
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 ...
user avatar
15 votes
2 answers
3k 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 ...
user avatar
  • 12.3k
14 votes
1 answer
930 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)$ ...
user avatar
  • 532
13 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 ...
user avatar
  • 249
12 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 ...
user avatar
  • 221
11 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 ...
user avatar
  • 121
10 votes
1 answer
433 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,...
user avatar
9 votes
2 answers
726 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 ...
user avatar
  • 568
9 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,...
user avatar
  • 9,800
8 votes
3 answers
1k 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 ...
user avatar
  • 181
8 votes
2 answers
457 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 ...
user avatar
  • 225
7 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)}}$ ...
user avatar
  • 553
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 ...
user avatar
  • 223
7 votes
2 answers
525 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 ...
user avatar
7 votes
0 answers
157 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 ...
user avatar
  • 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 ...
user avatar
6 votes
1 answer
209 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 ...
user avatar
  • 293
6 votes
1 answer
241 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$ ...
user avatar
  • 3,614
6 votes
2 answers
512 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 ...
user avatar
6 votes
1 answer
153 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 ...
user avatar
6 votes
1 answer
516 views

Why is combinational logic called so?

What is the significance of the word "combinational" in combinational logic?
user avatar
6 votes
1 answer
241 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 ...
user avatar
  • 63
6 votes
1 answer
238 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 ...
user avatar
  • 163
6 votes
0 answers
294 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 ...
user avatar
  • 161
6 votes
0 answers
422 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 ...
user avatar
6 votes
0 answers
218 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 ...
user avatar
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? ...
user avatar
  • 223
5 votes
1 answer
234 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$...
user avatar
  • 992
5 votes
1 answer
799 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 ...
user avatar
  • 3,458
5 votes
1 answer
346 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 ...
user avatar
  • 557
4 votes
1 answer
519 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 ...
user avatar
  • 141
4 votes
2 answers
218 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 ...
user avatar
  • 167
4 votes
1 answer
203 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} ...
user avatar
  • 211
4 votes
1 answer
103 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 ...
user avatar
4 votes
3 answers
296 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, ...
user avatar
4 votes
1 answer
159 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 ...
user avatar
  • 2,131
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 ...
user avatar
  • 10k
4 votes
0 answers
74 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 &...
user avatar
3 votes
1 answer
854 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?
user avatar
3 votes
2 answers
312 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 \...
user avatar
  • 1,541