# Questions tagged [terminology]

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

93 questions
Filter by
Sorted by
Tagged with
193 views

### HyperLogLog: Why “Hyper?”

I was teaching the HyperLogLog estimator in class earlier this week and a student asked where the “hyper” bit came from. I know that HyperLogLog is a refinement/improvement to the LogLog estimator, so ...
• 1,901
75 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 &...
• 501
1 vote
74 views

### Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains

Let ${\cal L}=\{Y_1,..., Y_k, X\}$ be a finite relational language such that $X$ is a unary relation name. Let $\phi(X,\bar{Y})\in{\cal L}$ be a first-order formula (the formula can have the equality ...
1 vote
182 views

### What does it mean by the statement: "a problem is hard to approximate "?

In most of the research papers that I have read so far, I often come across the statement of the following form: "the problem is hard to approximate within any factor smaller than some constant&...
• 1,389
155 views

### Adjective for: algorithm that outputs its input if it is one of its outputs?

Is there a well established adjective or name for an algorithm such that, given as input any of its own output, always outputs it unchanged? In other words, an algorithm such that it implements a ...
• 109
108 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
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 ...
• 181
161 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,131
189 views

### What is the name of this algorithm on direct acyclic graph?

I am trying to linearize the history of a git branch for display purpose. I want commits to be collocated by branch instead of simply displaying commits in the order given by the time of commit. In ...
• 123
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$...
• 992
1 vote
73 views

### Constraint terminology

If we want to pick a solution $S$ from a collection of items $C$ to maximize some function $f(S)$. The constraint that we pick at most $k$ item, i.e., $|S| \leq k$, is called the cardinality ...
• 239
158 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
144 views

### Maximize number of edges covered by an independent set of vertices

Smallest vertex cover which is also an independent set asks about finding an independent set that covers all edges. This problem is known as the independent vertex cover problem and is equivalent to ...
• 373
106 views

### Quick Sampling from Probability Distribution: Is there a name for this algorithm?

I'm trying to quickly sample from a near-uniform discrete probability distribution exactly once without calculating the entire CDF. Here's the algorithm. Givens: $N,$ the number of elements to ...
• 131
792 views

### On partitioning a collection into equivalence classes

Suppose I have a collection $A$ that I want to partition into equivalence classes, according to some equivalence predicate $E$. The naive algorithm for doing this is essentially recursive. It ...
• 531
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
125 views

### Complexity of a particular determinant

Suppose we have an $n\times n$ matrix $A$ with non-negative integer entries such that $\mathsf{Tr}(A^i)=0$ at every $i\in\{1,2,\dots,n-2,n-1\}$ and $\mathsf{Tr}(A^n)\neq0$, then from Trace-Determinant ...
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 ...
• 481
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 ...
• 221
1 vote
271 views

### What does "modulo" mean in SMT? [closed]

Very simple question, for which I failed to find an explanation: what does "modulo" mean in the "Satisfiability Modulo Theories"?
• 149
734 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
220 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
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)}}$ ...
• 553
855 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,331
276 views

### Terminology for complete k-partite graph where k is not fixed

Is there a better term for "complete k-partite graph" in the case where k is not fixed? If I say "complete k-partite graph", people tend to assume "for some particular k". In other words, what's a ...
• 916
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 ...
• 161
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 ...
• 249
111 views

### How to say "select the largest" when there can be more than one [closed]

Many algorithms include a step such as "select the largest number from a given numeric array", or "select the leftmost point from a given set of points", etc. In many cases, it is possible that the ...
• 1,826
436 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,...
314 views

1 vote
94 views

### Is there a name for this property in set-valued analysis or combinatorics?

I asked this question a few days ago on MO, but I haven't received an answer. So I thought I would ask here. I have also added a relaxed version of the question here. Let $F$ be a set-valued, finite-...
• 779
808 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,458
768 views

### Name this list-of-lists data structure

Is there a canonical name for the following data structure for list of lists? Suppose we have got a list of length $Z$ of finite lists $[a_0,\dots,a_n], [b_0,\dots,b_m], [c_0,\dots,c_o], \dots$ of ...
• 1,145
174 views

### Term for a "rooted" directional graph?

Consider an acyclic directed graph in which a traversal from any node in the graph must eventually end at some terminal node R. Borrowing from tree-based vocabulary, I would tend call this the "root" ...
• 123
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, ...
• 258
738 views

### what is "one-to-one reduction from a function f to another function g"

I am reading a paper called "Rational Proof". It mentioned the following one-to-one reduction. I cannot google an introduction of it. An excerpt from the paper. "Recall that a one-to-one reduction ...
• 1,423
402 views

### Difference between Stencil -structures and Cellular Automata Category-theoretically?

Definitions Stencil = "For a given point, a stencil is a pre-determined set of nearest neighbors (possibly including itself)." (source) Wikipedia's definition (source) = It looks ...
• 71
190 views

### Labels for terms in the lambda calculus

In the lambda calculus, are there commonly accepted names for $x$ and $M$ when they appear in $\lambda x [M]$ ? Something along the lines of "binder" and "bindee"?
• 133
513 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
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} ...