Questions tagged [terminology]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
70 views

What Pure Type Systems have dependent types

What precisely are dependent types? Is it a syntactic property of some type system? This seems to suggest that dependent types are defined through phase distinctions. For example, if a variable is ...
Trebor's user avatar
  • 335
2 votes
1 answer
45 views

Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?

There seems to be a slight difference in terminology among a couple of different traditions within theoretical computer science. To have a quantum computer simulate the Hamiltonian evolution of $\exp(...
Mark S's user avatar
  • 1,083
1 vote
0 answers
84 views

What is a "strongly complementary pair" of primal/dual solutions to a linear program?

While trying to understand this paper by Hammer, Hansen and Simeone, I came across some terminology I was unfamiliar with: the notion of a "strongly complementary pair". For a linear program ...
RubenVerhaegh's user avatar
3 votes
0 answers
205 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 ...
templatetypedef's user avatar
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 &...
Ville Salo's user avatar
1 vote
0 answers
86 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 ...
Erfan Khaniki's user avatar
2 votes
2 answers
166 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 ...
fgrieu's user avatar
  • 109
4 votes
1 answer
130 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 ...
Dan Staley's user avatar
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 ...
Robert's user avatar
  • 181
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 ...
Vanessa's user avatar
  • 2,151
2 votes
1 answer
203 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 ...
amirouche's user avatar
  • 123
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$...
C.P.'s user avatar
  • 992
1 vote
2 answers
79 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 ...
polar_bear_cheese's user avatar
7 votes
0 answers
167 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 ...
sirolf's user avatar
  • 201
3 votes
0 answers
146 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 ...
elexhobby's user avatar
  • 373
3 votes
1 answer
113 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 ...
k_g's user avatar
  • 131
2 votes
1 answer
1k 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 ...
kjo's user avatar
  • 531
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 ...
Alan Wolfe's user avatar
2 votes
0 answers
129 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 ...
user avatar
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 ...
Dolphin 613 Motorboat's user avatar
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 ...
molyss's user avatar
  • 231
1 vote
0 answers
287 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"?
Roman Susi's user avatar
9 votes
2 answers
788 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 ...
John D.'s user avatar
  • 568
4 votes
2 answers
247 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 ...
Rhymoid's user avatar
  • 167
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)}}$ ...
phs's user avatar
  • 565
3 votes
1 answer
863 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?
Chad Brewbaker's user avatar
0 votes
3 answers
281 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 ...
dspyz's user avatar
  • 916
6 votes
0 answers
302 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 ...
J Marcos's user avatar
  • 161
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 ...
alecbz's user avatar
  • 269
-4 votes
1 answer
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 ...
Erel Segal-Halevi's user avatar
10 votes
1 answer
476 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
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 \...
Max's user avatar
  • 1,561
6 votes
1 answer
230 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 ...
beta's user avatar
  • 293
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 ...
Austin Buchanan's user avatar
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 ...
Vijay D's user avatar
  • 12.6k
14 votes
1 answer
999 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)$ ...
David G's user avatar
  • 532
6 votes
1 answer
579 views

Why is combinational logic called so?

What is the significance of the word "combinational" in combinational logic?
Rob Jensen's user avatar
17 votes
1 answer
707 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 ...
Arindam Pal's user avatar
  • 1,591
1 vote
1 answer
178 views

Set of functions computable in polynomial time

I write paper and I want to distinguish between the class of decision problems which can be decided in polynomial time and the class functions which can be computed in polynomial time. The first is ...
Joachim's user avatar
  • 513
6 votes
1 answer
284 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 ...
IV1's user avatar
  • 63
12 votes
3 answers
4k 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 ...
kloop's user avatar
  • 131
-3 votes
1 answer
541 views

Name for terminals on the left-hand side of grammar rules? [closed]

Consider rules as they are used for context-sensitive languages: $\alpha A \beta \rightarrow \alpha \gamma \beta$ If $\alpha$ is always empty, we have right-context sensitive grammars: $A \beta \...
user avatar
1 vote
0 answers
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-...
Ankur's user avatar
  • 779
5 votes
1 answer
950 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 ...
David Harris's user avatar
  • 3,488
2 votes
0 answers
770 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 ...
shuhalo's user avatar
  • 1,165
2 votes
1 answer
176 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" ...
apsillers's user avatar
  • 123
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, ...
Paul Wagland's user avatar
2 votes
3 answers
822 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 ...
Peng Zhang's user avatar
  • 1,453
2 votes
2 answers
414 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 ...
hhh's user avatar
  • 71
3 votes
2 answers
193 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"?
mshang's user avatar
  • 133