Questions tagged [terminology]
questions about definitions, terms, and common names in theoretical computer science.
16
questions with no upvoted or accepted answers
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
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 ...
- 161
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
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
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
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
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
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
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
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
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
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 ...
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
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
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
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