Questions tagged [terminology]
questions about definitions, terms, and common names in theoretical computer science.
16
questions with no upvoted or accepted answers
7
votes
0answers
155 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 ...
6
votes
0answers
288 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 ...
6
votes
0answers
421 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 ...
6
votes
0answers
211 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 ...
4
votes
0answers
65 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 &...
3
votes
0answers
158 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 ...
3
votes
0answers
143 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 ...
3
votes
0answers
204 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 ...
2
votes
0answers
122 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 ...
2
votes
0answers
758 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 ...
2
votes
0answers
178 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
vote
0answers
61 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 ...
1
vote
0answers
149 views
What does it mean by the statement: “a problem is hard to approximate ”?
In most of the research papers that I have read so far, I often come across the statement of the following form: "the problem is hard to approximate within any factor smaller than some constant&...
1
vote
0answers
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-...
1
vote
0answers
198 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 ...
0
votes
0answers
212 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
