Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
1,052
questions
0
votes
1answer
28 views
Is Conjunctive Normal Form or not?
I have one formula that I do not understand why it is CNF and one that is not CNF, namely.
p && !q (NOT NCF)
and
!!p(CNF).
According to the exercise where I found these examples, 1 is not ...
0
votes
1answer
23 views
Map data structure terminology
I'm looking for the correct terminology in regard to map (dictionary) data structure.
When I'm talking about the semantics of the values stored in map in the direction from keys to values, I'd say, ...
0
votes
0answers
10 views
Anthology of term indexing
I'm interested in finding the most appropriate analogy of a data structure to describe organization/access of genetic information in cells. We humans have 23 pairs of chromosomes - each pair ...
0
votes
1answer
27 views
Find subgraphs that can only be reached by two nodes
I want to find subgraphs in a graph that are only connected to the rest of the graph by two nodes; for example, node A is connected to the rest of the graph, as well as node F, but nodes B-E are only ...
1
vote
1answer
22 views
What is a good reference for NP hardness in the machine learning/optimization/operations research context?
I am reading some papers in machine learning and at the very beginning (introduction) you will see statements of theorems that says, for example:
Theorem 1.1. For any constant ϵ > 0, it is NP-hard ...
1
vote
0answers
22 views
Calculus for Communicating Systems vs. Calculus of Communicating Systems
Robin Milner uses both terms: Calculus for Communicating Systems and Calculus of Communicating Systems and, AFAIK, writes CCS for both. Is there any difference between the two? Is there a difference ...
4
votes
1answer
89 views
Origin of “Cookie” in Computing?
"Cookies" are a user-facing computing construct. They are codified in many technical specifications, including the earliest reference in an HTTP spec, RFC 2109, published February 1997.
Many ...
0
votes
1answer
50 views
How to properly name the two types of RAM in a Paper?
How do I name VRAM and RAM properly in a paper?
"Video RAM" is clear but the "normal" RAM? Is it called "CPU RAM" or "Processor RAM" or "Main RAM" or ...
3
votes
1answer
194 views
Does the term “continuity” have a different meaning in maths and in CS?
I ask this question because of some statements in the question "What is the 'continuity' as a term in computable analysis?" making me suspicious.
I'm engineer, not computer scientist, so I ...
1
vote
1answer
58 views
Is there a name for X when X bitwise OR Y is Y?
I'm wondering if there is a mathematical or computer science term for a number X such that Y | X = Y? For example:
...
6
votes
4answers
4k views
What is it called when f(g(x)) = x?
There are a couple of function pairs which give the identity when composed, e.g.,
decrypt(encrypt(value)) == value
...
0
votes
1answer
43 views
Is there any official terminology about something like double quotes “” grammar?
In many programming language string is a token.
For example:
...
3
votes
0answers
59 views
What's the meaning of linguistics?
In the programming language theory world, there are two important terminologies, i.e syntax, and semantics.
I can understand these two terminologies:
syntax is about sentence's structure (e.g. a valid ...
0
votes
1answer
40 views
Consistent theory based on L and not(A->A) is a theorem
I am working on this problem in which I have a theory $T$ based on language $\mathcal{L}$ and the only information we have is that T is consistent and $\vdash \lnot(A \rightarrow A)$. Given this ...
0
votes
1answer
41 views
If X is polynomial-time reducible to Y and X is polynomial-time reducible to Z then Y is polynomial-time reducible to Z?
If $X$ is polynomial-time reducible to $Y$ and $X$ is polynomial-time reducible to $Z$,
$Y$ is polynomial-time reducible to $Z$?
If $X \leq_p Y$ and $X \leq_p Z$ then $Y \leq_p Z$?
True, false or we ...
-1
votes
1answer
35 views
If X is in NP then $\overline{X}$ is in NP. True, false or “we don't know”? Why?
If X is in NP then $\overline{X}$ is in NP.
True, false or "we don't know"? Why?
-3
votes
1answer
41 views
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
Is this true, false or "we don't know"? Why?
5
votes
2answers
254 views
Graph coloring variation
Are there variations of the classic graph coloring problem that the number of neighbors in the same color is limited but not zero (in the original problem the limit is zero)?
Problem: Given a graph $G$...
5
votes
1answer
272 views
How to pronounce “P/poly”?
Another question is about the reasons for calling P/poly "P/poly". My question is instead about its (verbal) syntax rather than its compositional semantics:
How is "P/poly" pronounced (in English)?
...
0
votes
0answers
16 views
Term for language that abstracts program location?
What is the technical term that describes a programming language that abstracts (or at least largely abstracts) the machine location of programs? I’m thinking here specifically of the evolution of ...
1
vote
0answers
25 views
Origin of GUI terminology
I'm wondering where the GUI terminology like modal dialogue comes from.
Who first used these terms? Is there a paper or a book, or was it just sw?
4
votes
2answers
89 views
Why is the second operation of a Monad called bind?
I understand how monadic computation works, I am just wondering where does the name come from. I cannot relate the thing that the bind operator actually does (i.e. ...
1
vote
1answer
45 views
Why F-bounded polymorphism and F-bounded quantification are called, well, F-bounded
It's claimed in Wikipedia that:
F-bounded quantification or recursively bounded quantification,
introduced in 1989, allows for more precise typing of functions that
are applied on recursive ...
3
votes
0answers
604 views
Backtracking vs Branch-and-Bound
I'm getting a bit confused about the three terms and their differences: Depth-First-Search (DFS), Backtracking, and Branch-and-Bound.
What confuses me:
Stack Overflow: Difference between '...
2
votes
2answers
45 views
Does the word “efficient” usually refer to polynomial time or polylogarithmic time?
This question is strictly about terminology.
I'm not an expert in CS, but I've almost always seen the word "efficient" applied to an algorithm to mean "of polynomial runtime". E.g. this question and ...
1
vote
1answer
28 views
to bail out vs to back out
In a CS context, I have often come across the expression to back out meaning to say that a function is returned from before performing its actual task, as in this imaginary code comment:
...
1
vote
1answer
44 views
The characterization of a problem as PSPACE-complete is …?
Let's assume that you found out that some problem $\mathit{\Pi}$ is PSPACE-complete (with respect to your favorite kind of reductions, say, logspace reductions). However, as there are dozens of well-...
0
votes
0answers
24 views
What is the meaning of “a polynomial amount/number of operations” in these contexts? [duplicate]
I am currently reading the book ''The Outer Limits of Reason'' and encountered a description about which I am very confused. I am afraid to say, this may be due to the fact that I am not a native ...
0
votes
2answers
86 views
IS there a consensus on the definition of a computer program in CS literature and if so, what is it?
The following is what I came up with from my synthetic prior research but I might be wrong.
I understand it is possible to reduce any computer "program", in a maximal reduction(?), to these features:
...
2
votes
1answer
183 views
Name for sorting algorithm “while not sorted, swap the FIRST unordered pair”
A typical bubble sort steps through all pair indices until it reaches the end of the list, then starts a new pass.
For a toy problem, we have a variant that just performs the first available swap in ...
27
votes
2answers
9k views
Is there a name for the class of algorithms that are the most efficient for a particular task?
This would be analogous to the Kolmogorov complexity of a string, except that in this case, I'm interested in the algorithm that solves a given problem using the least number of steps.
We would ...
1
vote
0answers
62 views
What are precisely computational effects?
I'm really confused with definition of computational effects. What I knew and understood about computational effect were only that they're impure computation, but someone noticed me that computational ...
0
votes
0answers
19 views
Internal & external fragmentation
Given five memory partitions 200kB, 600kB, 250kB, 450kB and 500kB which are fixed
and in order. processes of 212kB, 517kB, 115kB and 430kB in order.
In First-Fit order
212 kB --> 600 kB partition (...
1
vote
1answer
47 views
trace vs. computation vs. run vs. execution vs. walk
Many folks use the terms "trace", "execution", "computation", "run", "walk" ... interchangeably when they speak about state machines with labeled transitions. Does any work distinguish between these ...
1
vote
2answers
115 views
Is Turing machine a scientific theory in CS?
The English Wikipedia article about Turing machine opens with:
A Turing machine is a mathematical model of computation that defines
an abstract machine,[1]
As a Hebrew speaker, I read a similar ...
0
votes
1answer
37 views
Is there a name for a graph whose vertices consist of edges of an existing graph connected by an edge if they shared a common vertex?
I was wondering if there is a name for this construction:
Take a graph $G$ and construct a new graph $G'$ in which the edges of $G$ now become vertices, and "vertices become edges" in the sense that ...
1
vote
0answers
32 views
Meaning of “uniformly computably enumerable in m”
Nies, in Computability and Randomness, p. 6, defines "uniformly computably enumerable":
A sequence of sets $(S_e)_{e\in\mathbb{N}}$ such that $\{\langle e,x \rangle : x \in S_e \}$ is c.e. is ...
1
vote
0answers
26 views
What is the maths name for a set which contains the Domain and Codomain of a function? [closed]
Im interested in this so that I can name a type parameter in a program I'm writing.
There is function that that has three parameters.
D, Domain
C, Codomain
X, where D is a subset of X and C is a ...
0
votes
2answers
170 views
Does the callback concept of programming have any basis in computer science?
Although I seriously code with computer languages in general since 2010 and as an amateur programmer with programming languages in particular since 2015 (primarily Bash and JavaScript imperative ...
0
votes
1answer
43 views
What is the result of a reduction operation called?
Is there a commonly used term for the result of a reduction operation?
"reductant" does not quite sound right...
0
votes
1answer
61 views
Exact meaning of metalinguistic variable
Consider the following BNF
<join-command> ::= <string> + <string>
In this context <join-command> and <...
2
votes
1answer
710 views
What's the difference between phi and lambda in regular expression?
I've been learning on Formal Languages and Automata of Peter Linz(6th edition).
In the chapter 3 of this book, it explains the primitive regular expression.
But I don't know what is the difference ...
3
votes
1answer
144 views
maximum coverage version of dominating set
The dominating set problem is :
Given an $n$ vertex graph $G=(V,E)$, find a set $S(\subseteq V)$ such that $|N[S]|$ is exactly $n$, where $$N[S] := \{x~ | \text{ either $x$ or a neighbor of $x$ ...
3
votes
1answer
925 views
How can Lagrange Multipliers and Penalty Method be applied to optimize algorithms?
I have a programming assignment which I was told that is solvable with some DP algorithm. The question is a variant of LIS problem where at most $k$ exceptions (restarts) are allowed.
But I know that ...
0
votes
0answers
14 views
Is the standard terminology “logic operation” or “logical operation”?
I've heard both terms "logic operation" or "logical operation" used. Is either more common?
0
votes
0answers
104 views
Was there an attempt to create a programming language aimed for maximal abstraction?
I am trying to understand if a programming language can have totally or almost totally the abstraction level shared between generally all human languages so that it would allow a human to code a ...
1
vote
1answer
311 views
Difference between task and process
I'd like to know which is the difference between a task and a process in computer science. I'm studying a course on real-time systems and there are some definitions that I don't know.
Thank you in ...
1
vote
1answer
32 views
WebHook versus API
I've read many blogs about this but I still get somehow confused, specially why a webhook is a thing vs an API and not just a subset of API.
The way I interpret from most places (and interpret is ...
1
vote
1answer
17 views
What category does questions like “Given n points on 2D plane find …” belong to
Not after a specific answer, do following questions belong to same set of problem types?
Given n points in on 2D plane, find 4 or 5 , or m subset of points with less total distant to each other than ...
0
votes
0answers
16 views
Variable that takes values of $\left\{0, 1\right\}$ is called binary. How about variable that takes values of $\left\{-1, 1\right\}$?
Variable that takes values of $\left\{0, 1\right\}$ is called binary. How about variable that takes values of $\left\{-1, 1\right\}$? Is there a specific name for such variable? I search over the web ...
