Questions tagged [terminology]

Questions about how specific notions have to be understood as well as conventions of notation.

Filter by
Sorted by
Tagged with
3 votes
1 answer
59 views

Is possible to have a "pointer" to a tree node in a functional language?

Suppose I have the following structure definition in C: struct node { int value; struct node *parent, *left, *right; } If I want to represent a specific ...
user avatar
  • 131
23 votes
3 answers
3k views

Array access is O(1) implies a fixed index size, which implies O(1) array traversal?

Arrays are generally presented as data structures with $\Theta(N)$ traversal and $\Theta(1)$ random element access. However, this seems inconsistent: if array access is really $\Theta(1)$, this means ...
user avatar
0 votes
3 answers
83 views

Is there a notation for types?

Is there a notation for statements like the following: If both operands are of type int, then the result is of type int. If ...
user avatar
  • 101
1 vote
0 answers
30 views

Is There a Term for "Factoring" a Graph by an Equivalence Relation on Nodes?

I have a coding problem I'm running into that feels like it's solved: Given a (directed) graph, and an equivalence relation on nodes, merge the equivalent nodes in a way that preserves the graph ...
user avatar
  • 111
0 votes
0 answers
14 views

Why is LSTM hidden state called hidden?

If I undersand correctly, in a LSTM, the output is the concatenation of the consecutives hidden states $\text{output} = concat_{1\leq ï\leq n}(h_i)$. But then why are those hidden states $h_i$ called &...
user avatar
  • 126
0 votes
0 answers
22 views

If verify() -> valid, then validate() -> what?

Invalid blocks will be detected and rejected because it is difficult to compute a valid block, but computationally easy to verify one. From: p. 23 of ‘Blockchain Technology Overview’ National ...
user avatar
  • 101
0 votes
0 answers
27 views

Is copying and pasting a sort of object embedding?

If I copy a picture and paste it into Microsoft Word, would there be the difference if I embedded the same picture into another Word file ? Are they both object embedding?(As the object is saved in ...
user avatar
3 votes
1 answer
76 views

What is the formalism used to describe optional arguments called?

Most command line tools have an usage described by using square brackets for optional parts and just writing out required parts (like in regexes) for example: foo [opt1[opt2...]] req1 req2 [opt3...] ...
user avatar
0 votes
1 answer
30 views

Does a straightforward algorithm refer to the algorithm which intuitively solves a specific problem?

I'm trying to figure out what is a straightforward algorithm. The following pseudocode comes from section 4.2 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson,...
user avatar
  • 576
0 votes
0 answers
29 views

How can I generate all combinations of 2 sets of unique numbers? How are those called?

I want to generate 2 sets from N elements. Sets must be unique in the combination of sets Numbers must not repeat across the 2 sets Sets can have any amount of numbers, but must not be empty ...
user avatar
  • 101
1 vote
0 answers
21 views

Is there a word for a property of an algorithm where the output of the algorithm does not depend on the order of the input?

I'm looking for a word to describe an algorithm that takes an ordered list as input, where the output depends on the content of the list but not the order. A sorting algorithm on integers would be an ...
user avatar
0 votes
0 answers
50 views

What is a computational problem?

I'm reading Sipser's "introduction to the theory of computation" book. Even though in many places the phrase "computational problem" appears there is no definition of it. How is it ...
user avatar
  • 101
0 votes
0 answers
36 views

what's the differenece between finite state automaton and finite state automata

Upon googling all I get is the definition of finite-state automaton but what's the difference between it and finite-state automata or are they the same
user avatar
0 votes
2 answers
39 views

Is there a standard or model or taxonomy of programming languages different than machine-threshold-highlevel?

I understand that there are three types of programming languages: Machine languages Assembly languages high-level languages And that: Machine languages have no abstraction Assembly language have ...
user avatar
0 votes
0 answers
53 views

Set, then get, or first get, then set?

In some abstract programming languages there is a concept "setter and getter". Generalizing, should this be the opposite, i.e. "Getter and setter"? I would theorize that one should ...
user avatar
2 votes
0 answers
45 views

What is the etymology of "swizzle"?

The word swizzle can refer to an operation performed in GPU algorithms: [The] ability to compose vectors by arbitrarily rearranging and combining components of other vectors. Swizzle (computer ...
user avatar
1 vote
0 answers
39 views

Is try...catch a control flow pattern?

Is try...catch a control flow pattern such as if-than-else-elseif or ...
user avatar
  • 11
3 votes
2 answers
57 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 ...
user avatar
  • 5,032
1 vote
0 answers
31 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 ...
user avatar
  • 5,032
7 votes
2 answers
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 ...
user avatar
  • 576
0 votes
1 answer
13 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 ...
user avatar
8 votes
11 answers
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 ...
user avatar
0 votes
1 answer
21 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 ...
user avatar
  • 3
2 votes
1 answer
37 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?
user avatar
0 votes
1 answer
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 ...
user avatar
2 votes
1 answer
42 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" ...
user avatar
0 votes
0 answers
24 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 ...
user avatar
1 vote
1 answer
33 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 ...
user avatar
  • 113
1 vote
2 answers
84 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 "...
user avatar
  • 51
0 votes
1 answer
17 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 ...
user avatar
7 votes
1 answer
115 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 ...
user avatar
1 vote
0 answers
37 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....
user avatar
  • 121
2 votes
1 answer
200 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. ...
user avatar
  • 21
0 votes
0 answers
50 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 ...
user avatar
  • 1
1 vote
1 answer
56 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....
user avatar
0 votes
1 answer
42 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 ...
user avatar
0 votes
1 answer
75 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) ...
user avatar
1 vote
0 answers
19 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 ...
user avatar
  • 111
0 votes
1 answer
65 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 ...
user avatar
0 votes
1 answer
104 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}$...
user avatar
0 votes
1 answer
40 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 ...
user avatar
2 votes
0 answers
31 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 ...
user avatar
2 votes
2 answers
86 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 ...
user avatar
0 votes
0 answers
29 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 ...
user avatar
  • 719
-1 votes
1 answer
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): ...
user avatar
  • 113
3 votes
1 answer
47 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 ...
user avatar
1 vote
1 answer
26 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.) ...
user avatar
  • 115
1 vote
1 answer
46 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 ...
user avatar
0 votes
0 answers
34 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 (...
user avatar
  • 167
0 votes
1 answer
59 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?
user avatar

1
2 3 4 5
23