Questions tagged [terminology]
questions about definitions, terms, and common names in theoretical computer science.
94
questions
2
votes
1
answer
42
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(...
- 1,063
1
vote
0
answers
69
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 ...
3
votes
0
answers
199
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,921
4
votes
0
answers
76
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
1
vote
0
answers
83
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 ...
- 322
2
votes
2
answers
164
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
4
votes
1
answer
126
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
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
4
votes
1
answer
166
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
2
votes
1
answer
200
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
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
1
vote
2
answers
78
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 ...
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
3
votes
0
answers
145
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
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 ...
- 131
2
votes
1
answer
941
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
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
2
votes
0
answers
127
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 ...
user34945
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
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
1
vote
0
answers
283
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
9
votes
2
answers
777
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
4
votes
2
answers
235
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
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
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,351
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 ...
- 916
6
votes
0
answers
300
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
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
-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 ...
- 2,044
10
votes
1
answer
468
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
3
votes
2
answers
333
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
6
votes
1
answer
224
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
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
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.5k
14
votes
1
answer
975
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
6
votes
1
answer
555
views
Why is combinational logic called so?
What is the significance of the word "combinational" in combinational logic?
- 63
17
votes
1
answer
695
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
1
vote
1
answer
177
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 ...
- 513
6
votes
1
answer
276
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
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
-3
votes
1
answer
536
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 \...
user12156
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-...
- 779
5
votes
1
answer
906
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
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 ...
- 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" ...
- 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, ...
- 258
2
votes
3
answers
802
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,443
2
votes
2
answers
407
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
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"?
- 133
6
votes
2
answers
530
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