Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
1,066
questions
1
vote
0answers
19 views
Given a vertex in a digraph, is there a standard term for (the vertices reachable from it) union (the vertices reaching it)?
Question in title. Looking for whether there is a term that is, if not widely understood, at least citeable to a source.
This is equivalent to asking for the set of nodes that are comparable to the ...
2
votes
2answers
77 views
What makes a computer program modular?
Consider:
Constants and variables
If-then-else-elseif statements
Procedures and loops
The very fact that a program is comprised of two or more files (instead just from one large file)
Each one of ...
0
votes
0answers
24 views
Is the name 'class' from 'Complexity class' came from ZF set theory?
I just want to know if people in the complexity initiated the name 'class' because the term 'class' in Zermelo-Fraenkel set theory or not?
For me, I assume the answer is Yes; because it doesn't seem ...
-1
votes
1answer
44 views
Can a data abstraction use a class as a field, parameter, or return type?
I think that everyone will agree that the following class achieves data abstraction (hiding of its internal representation):
...
2
votes
1answer
41 views
Effectively decidable vs. noneffectively (or ineffectively) decidable
The introduction of https://www.sciencedirect.com/science/article/pii/0001870882900482 starts with the following sentence:
The word problem for commutative semigroups is effectively decidable.
I ...
1
vote
1answer
20 views
Is a constant literal an example of a built-in?
My understanding is that in a programming language, built-ins are bindings that exist without the user having to make them. (Like + to its referent, for example.)
...
1
vote
1answer
43 views
Terms related to optimal scheduling
I am studying a certain theoretical optimization problem related to scheduling, and I am confused by the different terms used in the literature for such problems. In particular, I found the following ...
0
votes
0answers
13 views
How do I call it when on Multi-threading I have a depency on a value that still doesn't exist?
On Multi-threading if I have multiple threads trying to access a single value I have a race condition.
What is the name given if the condition is that I'm trying to ...
0
votes
0answers
26 views
What do HC and HL (hamiltonian graph problems) stand for?
Hopefully, this question is fine.
I'm referring to the NP-complete problems regarding hamiltonian graphs.
I suppose the C in HC is from Cycle or Circuit. It seems like Circuit is more popular.
HL (...
0
votes
1answer
34 views
Are the definitions of loop in CS and in programming (standard/common) identical?
Are the definitions of loop in CS and in programming (standard/common) identical?
If not, what is the main difference / what are the main differences?
0
votes
1answer
34 views
What's the name of this packing problem?
I'm trying to pack sets of intervals, to find distinct buckets of intervals. The buckets should not be overlapping.
For example if I have these intervals:
...
2
votes
1answer
42 views
What is the difference between Partition and Division?
While reading graph theory, I came across different definitions where they use partitions and divisions, I was wondering, are these terms same or different?
Can anyone explain me their difference in ...
1
vote
1answer
27 views
Algorithmic information theory with stochastic algorithms?
Suppose we define a class of algorithms that is allowed to sample i.i.d. Bernoulli bitstrings of arbitrary length, and use these to generate outputs. If we are allowed to use algorithms like this, ...
1
vote
1answer
39 views
How does a computer direct the processing of information
So I'm reading Introduction to computing systems:From bits and gates to C and beyond, and the author states that a CPU is the mechanism that
...directs the processing of information. Which is ...
1
vote
1answer
48 views
How 'Avalanche Effect' got its name?
I wonder how or why Avalanche Effect got its name.
Avalanche Effect is a desirable property of cryptographic algorithms, wherein if an input is changed slightly (...
3
votes
0answers
56 views
Words of the same length in a language
Let $L\subseteq\Sigma^*$ be a language, where $\Sigma$ is a set, and let $n\in\mathbb N$.
I am wondering if there is some good terminology for
$L\cap\Sigma^n$.
Of course I could say "the set of ...
1
vote
2answers
95 views
Is there a name for an “array with no holes”?
How would you call an array [1, 2, 3, 4, 5, ...] that has (and ensures) the property of not having any undefined values through all its length.
"Dense" could work but it's not exactly what I ...
2
votes
1answer
49 views
Combinator terminology: What is “strong” about strong composition?
A strong composition operator seems to be very fundamental. (Hindley and Seldin use the notation S for "strong" composition combinator). It abstracts the pattern $f(x, g(x))$, i.e. a direct ...
1
vote
0answers
26 views
Correct terminology for $P1;P2$?
This question is about the correct terminology. Let $P1$ and $P2$ be two LOOP programs. Then $P1;P2$ is also a LOOP program, which executes $P1$ and then executes $P2$. Would this be called ...
10
votes
1answer
1k views
What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?
On an imperative programming language, let us consider the following program:
...
1
vote
1answer
46 views
What is the difference between Big O and asymptotic notation?
Are the two interchangeable or is there a difference?
0
votes
1answer
51 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
24 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, ...
1
vote
1answer
99 views
What does “associative” exactly mean in “n-way set-associative cache”?
I'm trying to grasp what does associative actually mean in n-way set-associative cache. I understand n-way set-associative cache as a concept; n is the degree of ...
0
votes
1answer
31 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
25 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
26 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
140 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
79 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
215 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:
...
7
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
50 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
64 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
47 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 ...
1
vote
2answers
100 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?
-2
votes
1answer
133 views
If X is polynomial reduction to Y and Y is in NP, then X is in NP? [duplicate]
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?
4
votes
2answers
271 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
298 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
17 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
136 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
78 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
954 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
59 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
54 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
48 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
2answers
90 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
201 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 ...
