Questions tagged [terminology]
questions about definitions, terms, and common names in theoretical computer science.
94
questions
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(...
- 849
1
vote
0
answers
80
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 ...
0
votes
1
answer
257
views
formal definition of "flowcharts"
I am looking for a formal definition of so-called "flowcharts" used as representation of programs or business processes.
Is there some good one around ?
Thx
JCLL
- 1
3
votes
0
answers
202
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 ...
- 2,121
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
1
vote
0
answers
84
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 ...
- 332
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 ...
- 101
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 ...
- 36.9k
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 ...
- 548
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 ...
- 4,771
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 ...
- 36.9k
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 ...
- 5,446
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 ...
CommunityBot
- 1
2
votes
1
answer
201
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 ...
- 1,653
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$...
- 16.9k
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 ...
- 1,046
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
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 ...
- 18.9k
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 ...
- 504
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
2
votes
1
answer
972
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
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 ...
- 653
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
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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
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 ...
CommunityBot
- 1
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 ...
- 36.9k
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 ...
CommunityBot
- 1
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)}}$ ...
CommunityBot
- 1
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?
- 1,703
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 ...
- 2,477
54
votes
11
answers
5k
views
If you could rename dynamic programming...
If you could rename dynamic programming, what would you call it?
- 36.9k
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 ...
CommunityBot
- 1
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 \...
- 4,796
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,...
- 10.2k
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 ...
CommunityBot
- 1
-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,745
2
votes
3
answers
811
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 ...
- 2,745
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 ...
- 4,306
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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)$ ...
CommunityBot
- 1
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"?
CommunityBot
- 1
6
votes
1
answer
564
views
Why is combinational logic called so?
What is the significance of the word "combinational" in combinational logic?
- 388
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 ...
- 11k
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 ...
- 4,631
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 ...
CommunityBot
- 1
2
votes
2
answers
411
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 ...
CommunityBot
- 1