# Questions tagged [terminology]

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

1,053 questions
Filter by
Sorted by
Tagged with
570 views

### Do I need to consider instance restrictions when showing a language is in P?

I have already shown that 3-colorable for an unrestricted graph is in NP, but I was thinking about the similar language defined as the set of all acyclic $G$, where $G$ such that $G$ is 3-colorable. ...
33 views

### Name of double sided search algorithms

I modeled the function double_sided_breadth_first_search after the ideas in "improving Dijkstra" in Cormen et al, and the OCW course on algorithms. Note that I expand the smaller boundary, in an ...
130 views

### NP-hard in what parameter?

I often read statements such as "the run-time of algorithm X is polynomial in m and n". Indeed, when a problem has two parameters, it is possible that the run-time of an algorithm is polynomial in one ...
36 views

### What do we mean by “spectral domain” in the context of graphs?

What do we mean by the spectral domain in the context of graphs? For example, I have heard that graph convolutions are easiest to define in the spectral domain. When it comes to the word "spectral", I ...
40 views

### Set of DAG vertices disconnecting a vertex from forbidden vertices

Let $v$ be a vertex with in-degree 0 in an (acyclic) DAG $G$, and let $F$ be a subset of $G$'s vertices (the "forbidden") vertices. Now suppose $U$ is a set of vertices such that every path from $v$ ...
134 views

...
42 views

### Turing Machine where branches are resolved via arbitrary operator

Alternating Turing Machines output Boolean values and combine the values returned by branches via the any/all operators. Is ...
46 views

### Terminology First-Order Logic

A graph $G$ is said to be a model of a first-order sentence $\varphi$ if $G$ satisfies $\varphi$. Now let $\varphi(x_1,...,x_r)$ be a first order formula with free variables $x_1,...,x_r$. What is ...
18 views

### Is there a more commonly-used term for “multi-pivoting”?

Consider the following computational problem (or rather, task): Given: An array of $A$ of (not necessarily distinct) elements from a fully-ordered finite domain An ordered sequence pivot ...
960 views

### Appreciation of the 5 state process model

I'm starting out in an Operating Systems module. I have a few understanding questions to think about, which will not be gone through in class. A process state model is an abstraction (or model) which ...
111 views

### Name of a tree with arbitrary number of branches at each fork point?

A binary tree is a rooted tree with the root having an indegree of 0 and all other nodes of 1. The outdegree is 0, 1 or 2 for all nodes. How do you call a rooted tree if the number of branches per ...
484 views

### Which AC-3 algorithm is being used here?

This is the illustration of the AC-3 algorithm for four queens from exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem by Md. Ahsan Ayub, Kazi A Kalpoma,...
428 views

### Is there a name for this priority queue data structure?

While watching a sports tournament, I noticed that the tournament tree looks a lot like a heap. I came up with the following data structure: A complete binary tree where the leaves are elements of ...
432 views

### Relation between semi decidable, undecidable and countable sets

I know that decidable problem: has both counting (bijection with $\mathbb N$) and membership algorithm (TM halts for both member and non member strings ) semidecidable problem: has counting ...
48 views

### What is the term for two file formats that describe the same amount of information?

I am working on file formats conversion. Some of them can be converted back and forth to others without losing any information (fields or precision of the numbers encoded), others file format do not ...
363 views

### What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute

If I were to pose the question: "Given a program $P$ containing statement $X$, will $X$ be executed (given enough runs with all possible inputs)?" This strikes me of being a relative of the Halting ...
2k views

### What is this data structure/concept where a plot of points defines a partition to a space

I encountered an algorithm to solve a real world problem, and I remember a class I took where I made something very similar for some for a homework problem. Basically it's a plot of points, and the ...
65 views

### Terminology for worst-case N-complexity on $O(1)$ insert after amortisation

Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews ...
114 views

### How broad is the meaning of “algorithm”?

This is a purely terminological question. The word algorithm, as I have learnt it refers to something like an "effective method, a sequence of steps, for doing something". There are alternative ...
26 views

### Complementary of graph invariant

Graph invariant is a property that holds for two isomorphic graphs. For example, degree sequence is graph invariant. We can write $d(G) \ne d(G') \Rightarrow G \ncong G'$, although $d(G) = d(G')$ ...
31 views

### Curiosity on system device nomenclature - Gaussian Mixture Models [closed]

Would not know if this is the best SE website to ask, but I could not find anything better, especially because the answer might involve a fair amount of computer science (although this is an ...
56 views

### What, if any, is the term for a node whose children are all leaf nodes?

More specifically, I'm interested to know if there is a term that describes a tree node that meets two conditions: - It has >= one child - Any children that it has are all leaf nodes.
32 views

### How literally is “optimization” or “optimization algorithm” used in CS?

I have been confronted with two meanings of the term "optimization" or "optimization algorithm": to find the absolute maximum in a set $X$ according to some criterion $f:X\to \mathbb R$ to find a "...
47 views

### What's the theoretical difference between class and type?

This question stems from my effort trying to learn ASN.1. After I went through the PKCS#1 standard for RSA cryptosystem and X.680~X.683 side-by-side, I noticed that, they've defined ...
137 views

### Do SLR(1) parsers have lookahead?

The SLR(1) parses AFAIK does not have any lookahead with it then why do we write it as SLR(1) and not as SLR(0). The thing about parsers which I read online taught me that if it's LR(K) then K ...
9 views

78 views

### AVL Rotations Abbreviations

I read that there are 4 types of rotations: Left rotation Right rotation Left-Right rotation Right-Left rotation What are the corresponding abbreviations: RL,LR,RR,LL? Is there a reference how to ...
35 views

### Linear ordering of all subsets of size k

I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\{1,\ldots, n\}$ into ...
97 views

### Name for the tree formed after collapsing cycles

What do you call a structure which becomes a tree after collapsing cycles (so the new vertices are the old faces)? For instance, the digraph (given by an NFA; ignore edge labels please) below becomes ...
46 views

### Is there a distinction between pointers and references? [closed]

If so, what are the similarities and differences between the two? I’ve only worked with properties while programming.
3k views

### Is “super-exponential” a precise definition of algorithmic complexity?

I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity. For instance, if an algorithm runs for $nC(n-1)$...
11k views

### Dynamic Programming vs Memoization

I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization. Am I ...
118 views

### How hash-table and hash-map are different?

In the context of CS, how the hash-table and hash-map are different? I was watching a part of "Algorithm with Swift" video in Udacity, and I discovered the terms "hash-table" and "hash-map" are ...
414 views

### Understanding the “ordering of the four types of edges” in DFS

The following is Exercise 22.3-6 from CLRS (Introduction to Algorithms, the 3rd edition; Page 611). Show that in an undirected graph, classifying an edge $(u,v)$ as a tree edge or a back edge ...
76 views

### Tree with alternating types of nodes

Suppose that I have a tree where each node is either of type A or type B. Nodes of type A ...
66 views

### Are the definitions of recursively enumerate equivalent?

There are a couple of definitions of recursively enumerable, for example in Judah: $A \subset \mathbb{N}$ is called r.e. if there exist a $\Sigma^0_1$ formula $\varphi(x)$ such that A:=\{n \in \...
68 views

### Is there any sort of formal definition of terms like 'data type', 'abstract data type', etc?

If not (because I assume not) is there some kind of reference or book that provides some theoretical foundation to these concepts? I've been learning about data structures and abstract data types for ...
511 views

### What makes a proof assistant a proof assistant?

You open a code editor, define a syntax with lambdas, a few primitives. Then you invent some nice computation rules, some cool typing rules, and write a corresponding interpreter and "type checker". ...
606 views

### Is every regular/context free langauge decidable in LogSpace?

I know all the regular languages are decidable but not sure whether it can be done in LogSpace.
394 views

### search problem vs optimization problem

This is mostly a terminological question: Is there a fundamental difference between "optimization problems" and "search problems"? Apologies if this is an obvious question As I ...
73 views

### What kind of logarithm does $\log$ mean in Wikipedia articles?

Sorry if this seems like a dumb question, but what what type of logarithm is $\log$ in Wikipedia articles? Cheers.
269 views

### FPTAS definition

I read that a fully polynomial time approximation scheme (FPTAS) has time complexity polynomial in the input size and also polynomial in $1/\epsilon$. However, this leaves some ambiguity. For example,...
281 views

### Why does everyone say that NFA guesses it's next state?

In the picture above e is an empty string, and a is a symbol from an alphabet. Every book or professor I have heard from, says than when we make transitions in the NFA, the NFA must guess which state ...
217 views

### Is “sparse subtree” an appropriate term for what I describe in this question?

Given a tree, with some nodes annotated, such that the annotations form another tree, I'm thinking "sparse subtree" is an appropriate term for describing the latter tree as it relates to the original ...
38 views

### Does data entropy depend on the arrangement of the characters in a file?

From what I understand data entropy controls the limit of data compression and it depends on the probability of the characters in the file. Assuming that we have a file of size 256 bytes containing ...