Questions tagged [terminology]
questions about definitions, terms, and common names in theoretical computer science.
94
questions
4
votes
1
answer
207
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} ...
- 211
1
vote
7
answers
4k
views
All recursive algorithms are inherently NOT-inplace, isn't it?
As recursive algorithms depend on the stack whose size is in almost all the cases depend on input, why don't we consider all the recursive algorithms as NOT-inplace algorithms?
Consider for example, ...
- 77
1
vote
1
answer
848
views
What do people mean by capabilities and capacities?
Someone made a casual remark to me about the terminology of capabilities and capacities, in the context of threads, processors and runtime systems, particularly their theoretical modelling.
For ...
- 11
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 ...
6
votes
1
answer
242
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 ...
- 163
6
votes
1
answer
155
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 ...
- 32k
6
votes
0
answers
425
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 ...
- 263
-6
votes
3
answers
442
views
How can I call functions that are not "first-class functions"?
I mean, is there an antonym for "first-class function"?
- 147
2
votes
1
answer
250
views
What is a totally ordered sort of sets of a partial order called?
Given a DAG, which can represent a partial order and has at least one topological sort.
For example the graph
>B
/ \
A >D
\ /
>C
has two ...
- 1,008
6
votes
0
answers
220
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 ...
- 13.6k
-1
votes
1
answer
294
views
Data representation and bit/time complexity
I have a simple technical question on multiplication of finite bit words. Say the number of bits of words that need to be multiplied is $O(\log{M})$ and say an hypothetical algorithm uses $O(\log{M})$ ...
- 2,208
3
votes
1
answer
266
views
Standard/Formal name for the graph
Given a connected graph $G =(V_1,V_2,E)$, such that there are no edges among the vertices in set $V_1$, however the other set $V_2$ can have edges in itself. There is actually a restriction for $V_2$, ...
- 725
1
vote
1
answer
72
views
Term for a correspondence of two point sets regarding their ordering in each dimension
Let there be two sets of points $S$ and $S'$ in $R^d$. $|S| = |S'|$, and for each point $s_i$ in $S$ it exists exactly one corresponding point $s'_i$ in $S'$, such that the ordering of ...
- 173
3
votes
0
answers
205
views
Name for relationship where one graph is a minor usually implies another is?
Let $G$ and $H$ be graphs with the following relationship: for some $k$, after you perform at least $k$ arbitrary subdivisions of the edges of $G$ (or the edges produced through subdivision), $H$ must ...
- 343
5
votes
1
answer
348
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 ...
- 557
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? ...
- 223
0
votes
1
answer
3k
views
vertex in a degeneracy ordering of a undirected graph
There is a step in Bron–Kerbosch algorithm
for each vertex v in a degeneracy ordering of G:
what is "a degeneracy ordering of G"? For example what is vertex in a degeneracy ordering in
this ...
- 109
3
votes
0
answers
377
views
Are grammars programs? [closed]
Are grammars programs? That is, are languages for grammar specification programming languages?
Update.
Motivation for the question is follows:
To know whether languages for grammars are programming ...
- 443
4
votes
1
answer
533
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 ...
- 141
10
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,...
- 9,850
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
user4877
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 ...
- 10.3k
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 ...
- 1,259
2
votes
1
answer
250
views
Terminology for types of universal computation
Some models of computation are universal in the sense they can compute any arbitrary computable function $f:\mathbb{N} \rightarrow \mathbb{N}$.
Other models are universal only as far as the input and ...
1
vote
0
answers
215
views
LALR grammars subsets
If LR(0) condition for a grammar G is formulated as follows:
Every state is either reduction or a shift state and it can't be both at the same time
if it is a reduction state, it contains exactly one ...
- 163
1
vote
2
answers
614
views
Bin allocation problem
Despite the warning from the StackExchange Question engine that this question appears subjective, I'm going to ask it anyway.
We have a script as part of an application at work which is responsible ...
- 113
17
votes
1
answer
388
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 ...
- 815
2
votes
2
answers
121
views
Asking optimal questions to differentiate object in set
I have a problem in mind and I am sure this is likely an area of active research, but am at a loss as to the correct terminology and thus unable to find any reference literature. It is best explained ...
- 835
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 -- ...
- 532
54
votes
11
answers
5k
views
If you could rename dynamic programming...
If you could rename dynamic programming, what would you call it?
2
votes
4
answers
994
views
How do you call a subsequence of consecutive elements ?
I wrote a function that returns the position of a given subsequence in a sequence. However, I just realized that I used the term "subsequence" incorrectly: according to Wikipedia, the elements of a ...
- 131
6
votes
1
answer
250
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$ ...
- 3,664
1
vote
1
answer
204
views
Has this online problem been studied before ?
Consider the following online problem:
For $\sigma$ and $k$ fixed, given a string of symbols from alphabet
$[1..\sigma]$, given one by one, guess a set $S$ of $k$ symbols such that the
next ...
- 2,733
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 ...
- 223
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?
- 323
8
votes
2
answers
553
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 ...
- 4,902
2
votes
3
answers
337
views
What is the name of this partition-indexed key-value data structure?
Consider a data structure that holds N elements having M partitions each holding N/M elements where M divides N. Each element has a key that satisfies an equivalence relation so as to index into one ...
- 123
2
votes
1
answer
219
views
Graph nodes preserving changes to the overall graph
I remember reading about a kind of Graph data structure, where every change to the the graph could be preserved. I don't remember exactly neither the name, neither a good description (if it was the ...
- 143
2
votes
1
answer
245
views
Searching for name of equivalence property in hamiltonian paths
This one has been bugging me for a while. A long time ago in undergrad, I noticed this while learning about TSP. Nobody recognized it and I basically gave up.
Given a hamiltonian path, any subpath ...
- 37
2
votes
0
answers
180
views
What are contravariant tensors of type m choose 0
I am not sure if the following question falls within the scope of this site; if it does not, I will request the moderators to take appropriate action
I have been going through Jin-Yi Cai's expository ...
- 1,953
-2
votes
1
answer
801
views
Is Perlin Noise a "fractal"? [closed]
I have an old Spanish CG book that calls Perlin Noise a "fractal structure". After reading this I couldn't deny it or confirm it. Is it a fractal structure? What would it Hausdorff dimension be?
- 97
8
votes
2
answers
462
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 ...
- 225
37
votes
2
answers
6k
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 ...
- 2,904
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 ...
- 629