Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
1,090
questions
2
votes
2answers
30 views
What does "lambda terms modulo convertibility" mean?
In "The Lambda Calculus - Its Syntax and Semantics" by H.P. Barendregt (WorldCat) is this statement, the first sentence of chapter 2 after the introduction chapter, so in a way this sets the ...
1
vote
0answers
26 views
What does "terms modulo" mean? [duplicate]
In "The Lambda Calculus - Its Syntax and Semantics" by H.P. Barendregt (WorldCat) the term "term modulo" is used, E.g.
The principal object of study in the λ-calculus is the set ...
7
votes
2answers
3k views
Is the Berkeley tutorial on Fibonacci trees using wrong figures?
I'm confused about the figures in a Berkeley tutorial on Fibonacci trees, which depicts fibtree(2) as
and fibtree(3) as
I thought fibtree(3) looks like the following
(the figure is adapted from ...
0
votes
1answer
12 views
What is the name of this content-addressing scheme?
Git seems to use the two most significant hex digits of a content hash as a directory name for content-addressable objects. The same two digits are left out of normal file names. I'm assuming the ...
7
votes
11answers
4k views
Real life examples of *zero* weight edges in graphs
The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously.
Yet, when I recently read here a question on real life example ...
0
votes
1answer
20 views
Understanding P, NP with an example decision problem
I was reading the definitions of p vs np in [this post] (What is the definition of P, NP, NP-complete and NP-hard?) and I was wondering about how to classify the example decision problem where you ...
2
votes
1answer
28 views
What is the outermost class 2^Σ* referring to on the Extended Chomsky Hierarchy?
After having searched a bit, it seems I can't find terminology or references for this outermost class, 2Σ* in blue -- see below. What is it describing?
0
votes
1answer
17 views
What does it mean to 'provide' an API call?
So I have a database pre-loaded with data related to food recipes and the assignment says:
'Provide an API call that allows us to specify an ingredient or set of ingredients and return full recipes ...
1
vote
1answer
40 views
Are bits (0/1) named "characters" anywhere in the literature?
I know that each character ("in the macro level") is comprised of at least two bits ("in the micro level").
But are these bits of this "micro, electrical-logical level" ...
0
votes
0answers
21 views
What is BB(n) terminology precisely saying about symbols, states, space, and steps involved?
This question is mainly about the clarification of the terminology BB(n), not how busy beavers work. It seems common to refer to busy beaver numbers like ...
1
vote
1answer
30 views
What makes 'interrupt vectors' vectors?
I've recently been learning about interrupt vectors, partly from this Wikipedia page.
I've understood that different processors will have different types of interrupts, and the interrupt vector table ...
1
vote
2answers
36 views
NFA has power to be in several states at once implies NFA has ability to guess about its input. How?
I agree that NFA has power to be in several states at once. It probably means that on same input, NFA can be on multiple states. But what I can't understand is how can we conclude from this that "...
0
votes
1answer
16 views
Word that describes text transformation into a code with data loss
I am working with a piece of software code which transforms a character array into a single integer. For example, if I have the array [ a, b, c ], then it becomes ...
7
votes
1answer
110 views
Does the concept of "side-effect" predate functional programming?
When I was reviewing a book, I saw that there's a sentence claiming "side effect is a term coming from the domain of functional programming". I would think that the concept existed before ...
1
vote
0answers
36 views
Terminology for multiply visiting walks of directed graphs
In phrasing an information model for consumption-optimized RDF-like data (full context at 1 for the curious), I'm looking for any established term for X as used here:
Given is a directed rooted graph....
2
votes
1answer
188 views
Topological sort with minimum maximal distance in array
I have a DAG that admits many possible topological sorts. I want to construct one that has the minimum maximum distance between a node and its neighbours in an array storing the nodes in sorted order.
...
0
votes
0answers
49 views
basic terminology
Suppose we have two computers whose performance is P1 and P2 respectively when P2=d⋅P1. What is the most accurate name for d? Is the term "transition factor" appropriate? Additional ...
1
vote
1answer
54 views
What does “linear” in Linear Temporal Logic refer to?
Consider the term linear temporal logic (in the meaning of linear-time temporal logic). In linear temporal logic, what does linear refer to:
to temporal or
to logic?
If I interpret http://en....
0
votes
1answer
41 views
Constraining function inputs; what concept/terminology am I looking for?
A function takes some set of inputs and creates a set of outputs; however there will be some set of invalid inputs. For example say we have F(a,b) => a / b and we constrain 'a' & 'b' to be ...
0
votes
1answer
49 views
Definition of static property of object in OOP
Grady Booch in Object-Oriented Analysis and Design with Applications says:
The state of an object encompasses all of the (usually static) properties of the object plus the current (usually dynamic) ...
1
vote
0answers
18 views
Does this Hamming-like algorithm for solving a permutation of an address space have a name?
I'm working on reverse engineering the bit stream format of an FPGA, in particular regarding the address translation of the BRAM (block RAM), but the algorithm could in general be used for any ...
0
votes
1answer
62 views
A program which works "digitally" and a program that works "analogue"
I have noted that in several very unrelated human natural languages, people often confuse the term "virtual" with "digital".
As for Computer Science, is it correct to categorize ...
0
votes
1answer
74 views
Halts for all rejects, but might accept/loop otherwise?
If a Turing machine halts for all rejects of L but might accept/loop otherwise, how is L's recognizability classified?
Recognizability
Decidability
${\langle L\rangle}$
${\langle \overline{L}\rangle}$...
0
votes
1answer
34 views
Can partially observable MDPs be fully observable nonetheless?
I've read through a few definitions of a partially observable environment/MDP, and I need confirmation whether the partial observability is really a generalization of a MDP (misnomer) and not a ...
2
votes
0answers
29 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
80 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
25 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
46 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
44 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
23 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
45 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
14 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
27 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
37 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
35 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
57 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
29 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
50 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
52 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
62 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
100 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
47 views
What is the difference between Big O and asymptotic notation?
Are the two interchangeable or is there a difference?
0
votes
1answer
79 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
363 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
51 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
32 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 ...
