Tagged Questions

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

learn more… | top users | synonyms

3
votes
0answers
49 views

Does any one know what this problem is called?

We are given finite sets $A$ and $B$ and a set $S\subseteq \mathcal{P}(A)$. The members of $\mathcal{S}$ may have arbitrary intersections with one another and their union is not necessarily $A$. ...
0
votes
1answer
28 views

Is there a name for the 'scope tree' organization?

I could describe JQuery as a library that allows you to easily select elements on and traverse the DOM, the DOM would be the name of the tree or organizational structure of the HTML. When you are ...
1
vote
0answers
12 views

Terminology for a partially unlinked doubly linked list?

Let's say you have a standard doubly link list implementation: struct List { int Number; struct List *blink; struct List *flink; }; and that you have ...
5
votes
1answer
326 views

What is the formal name for this algorithmic problem?

I'm doing some work on a problem and I'm finding it difficult to research it with out the actual name of the problem, since the problem I'm working on gives it it's own abstraction. The problem is ...
0
votes
0answers
16 views

What is the correct term for “time to establish a connection”

I don't remember what is the term for "time to establish a connection". For example in a smartphone, when I lost the wifi signal and the phone try to get mobile data connection it spends a bit of ...
3
votes
1answer
43 views

Where does the terminology of open addressing resp. closed hashing come from?

One of the basic methods of hashing is called "Open addressing, or closed hashing" according to wikipadia (and several books). Why the names "open" and "closed", and why these seemingly contradictory ...
2
votes
2answers
60 views

Understanding constraint formula concept in Java

JLS defined a concept called "constraint formula". There is a formal definition: Constraint formulas are assertions of compatibility or subtyping that may involve inference variables. The ...
2
votes
2answers
54 views

How is the number of states in a Turing machine bounded?

The definition of Turing machine says that the number of states is finite. However, I do not get how this can be true. Is the number of states in a Turing machine actually not fixed, that is not ...
-1
votes
0answers
18 views

What are logical/physical records and sectors?

I try to understand the following definitions but currently I feel like a sinking ship. For example: What is a record ? What is a logical- and physical-record ? Concerning the physical-record I ...
0
votes
2answers
62 views

What is the definition of a problem

In computation theory, when talking about the computability and complexity of a problem, what is the definition of a problem? How specific should a problem be? For example, can the followings all ...
1
vote
2answers
40 views

What is the set of operations of a Turing machine?

From https://en.wikipedia.org/wiki/Abstract_machine A typical abstract machine consists of a definition in terms of input, output, and the set of allowable operations used to turn the former ...
1
vote
1answer
23 views

Difference between a lambda term and a lambda expression

Is there any difference between a $\lambda$-term and a $\lambda$-expression? Looking at the recursive definitions on Wikipedia of $\lambda$-term and $\lambda$-expression, they are equivalent. But I ...
2
votes
2answers
91 views

Is it possible to obtain a total function by composition of partial functions?

This statement is Theorem 1.1 (page 39) of Computability, Complexity and languages by Martin Davis: If function $h$ is obtained from the (partially) computable functions $f$, $g_1$, $g_2$, ..., ...
2
votes
2answers
67 views

Is there a difference between perfect, full and complete tree?

Is there a difference between perfect, full and complete tree? Or are these the same words to describe the same situation?
4
votes
3answers
66 views

Is the height of the tree the number of edges or number of nodes?

I'm so confused by some of the theorems online about tree heights. Does tree height mean the number of edges or nodes? if nodes, does it include the node it is counting from? Can the height of a tree ...
4
votes
3answers
56 views

When problem A reduces to problem B, which problem is more complex?

When discussing complexity classes, when we say that problem $A$ reduces to problem $B$, are we saying that problem $A$ is at least as complex as problem $B$, or the other way around?
0
votes
0answers
24 views

Difference between parallel and concurrent buffering?

In double buffering there are two terms Concurrent buffering. Parallel buffering. What is the difference between them, answer with example will be appreciated.
0
votes
1answer
60 views

What is the difference between shortest distance and shortest path?

I am studying graph currently. I found a question, which asks for The List A[] which shows shortest distances between $V$ and every other vertex The List ...
3
votes
1answer
230 views

What is a partially computable function?

In the book Computability, Complexity, and Languages, Martin Davis writes in chapter two: A partial function is said to be partially computable if it is computed by some program. and also ...
-1
votes
1answer
38 views

What are activation records?

What are the open activation records of a recursive algorithm ? Edit: Activation records are the number of times that we call a function that is not finished yet. Correct? So we can find the number ...
-1
votes
1answer
25 views

Triangles incident on a vertex (Graphs)

I have a project that I am doing. The specification requires specific methods on a graph class. Two of the methods requires this: ...
2
votes
2answers
65 views

Terminologies of “Process calculus” and “Process algebra” [duplicate]

In the literature, the terms of "process calculus" and "process algebra" are often interchangeable. Meanwhile, it confused me. My questions are: Are there formal, standard, and ...
2
votes
3answers
121 views

What do f(x) and g(x) represent in Big O notation?

I have been reading about Big O notation. People writing about Big O often use the terms $f(x)$ and $g(x)$. For instance, I often see people write things like $f(x) = O(g(x))$ or $f(x) \in O(g(x))$. ...
0
votes
2answers
33 views

Recursion: base case vs. small version

I'm reviewing the definition of recursion and in my notes are two questions about a recursive problem. One question asks about the base case, the other one about the small version of the problem, I ...
-2
votes
1answer
44 views

What does “schema” mean? [closed]

In a relational model, a schema is something which specifies the name and data type of each field. The word "schema" is also used in "conceptual schema", "physical schema" and "external schema". ...
0
votes
0answers
16 views

Classification of one-dimensional CA based on the number of inputs each cell receives during an update?

Consider Wolfram's rule 30 and Wolfram's rule 62. In the case of rule 30, only two bits of information must be passed to each new cell in the CA during an update, while for Wolfram's rule 62, three ...
2
votes
1answer
43 views

How to vocalize hexadecimal numbers?

When I want to vocalize a hexadecimal number like 0x41, so I say "forty one in hexadecimal", "four, one in hex" or what? Or do you always have to calculate and say "65 in hexadecimal notation"? I feel ...
2
votes
1answer
22 views

Terminology about the word Function : General vs Computable

I've seen two different concepts referred to by the term "function": A small part of a program specified by the composition of constants and other functions as paramaters, such as the "functions" in ...
1
vote
2answers
82 views

Computation is effectively computable in theory and in practice

My big question is the following: What is the meaning of a computation being "effectively computable" (EC) in theory and in practice? In trying to understand these concepts further, I have a couple ...
-2
votes
1answer
37 views

What is a forwarding pointer? [closed]

I heard this terminology used today and haven't come across it before, could someone please explain? Are there any other terms/names that describe this concept?
6
votes
1answer
64 views

Etymology of time and space “complexity”

The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. ...
2
votes
2answers
85 views

Algorithms which are both deterministic and non-deterministic

I'm just starting my second year in computer science and one of my classes briefly touched upon deterministic vs. non-deterministic algorithms. This got me thinking - is there any use for algorithms ...
3
votes
0answers
27 views

Term for index-like data structures

There's a class of data structures where you preprocess some other data structure in order to answer queries about it more efficiently. That includes trivial things like sorting/hashing, less trivial ...
0
votes
1answer
27 views

minimum vertex set removal for edge-free graph

I'd like to know the name and the algorithm for the following problem which I'm guessing is a classic, but is slightly different from graph connectivity. Consider a undirected graph G=(V,E). What is ...
1
vote
1answer
35 views

Weakening and Contraction

Wikipedia says that weakening is a structural rule where the hypotheses or conclusion of a sequent may be extended with additional members and that contraction is a rule where two equal (or unifiable) ...
0
votes
1answer
80 views

Are dictionaries and associative arrays the same thing?

With respect to abstract datatypes (ADTs), are the terms "dictionary" and "associative array" perfect synonyms or are there slight differences between them?
1
vote
2answers
64 views

A recursively enumerable language and a recursively enumerable set

I am confused between these two terminologies: recursively enumerable language, recursively enumerable set. Do they have the exactly same meaning?
2
votes
1answer
63 views

Which article in front of O(.), Ω(.), …?

Writing a survey, I am confronted to a very difficult and -- I dare say -- deep issue: I have many sentences mentioning or stating results of the form "a $\Omega(\sqrt{n})$ lower bound", or "a ...
0
votes
1answer
94 views

What is difference between architecture and microarchitecture?

I am studying computer architecture. I would like to know the difference between the terms "computer architecture" and "microarchitecture".
3
votes
2answers
70 views

Does “output” always imply halting in computability?

$L = \{P : P(n)$ outputs $n^2$ for all $n \in N \}$ In questions of this nature, are we supposed to assume that "outputs" means "halts and outputs"? In modern programming languages, I can ...
5
votes
3answers
149 views

Difference between weak and strong AI

I'm trying to understand the difference between weak and strong AI. For an example, let's say we would pass the turing test - would it show strong AI or weak AI then? I don't believe that this is ...
4
votes
2answers
78 views

What is the definition of a $\Pi_1$-sentence?

What is meant when somebody says that a problem can be expressed as a $\Pi_1$-sentence? I know that for the arithmetical hierarchy, a $\Pi^0_1$-sentence is a sentence of the form $\forall n_1\forall ...
8
votes
2answers
31 views

What guarantees do “soft” real-time operating systems actually provide

I think I know what a "hard" real-time operating system is. It is an operating system with a scheduler that provides a contract with the application programmer. An application provides a deadline ...
0
votes
1answer
27 views

Grammars: is there some connection between non-terminals $S$ and $S'$?

Given a grammar such as the following, does $S'$ have some special meaning or does it just denote another non-terminal like $B$, $A$, $P$, $Q$ etc.? $$\begin{align*} S &\to aBS'\\ B ...
1
vote
0answers
38 views

What is regular about regular languages? [duplicate]

I am new to automata theory. I am well aware of the definition of regular language in automata, that is "a language is called a regular language if some finite automaton recognizes/accepts it" [MS]. ...
0
votes
1answer
50 views

What is the difference between symbol and enumerated datatypes?

I wonder what differences and relations are between symbol and enumerated types? A symbol is a primitive datatype whose instances have a unique human-readable form an enumerated type is a ...
5
votes
2answers
206 views

What is the connection between data structures and data types?

I have read some books and wikipedia, which seem to give not completely consistent definitions and notations. I try to understand the concepts, regardless of what they are called. Here are what I have ...
3
votes
1answer
176 views

What do queues and stacks correspond to in math?

Many (and I suspect all) abstract data types in CS correspond to some math concepts, and even share the same names, for example, set, map, record/tuple, .... As abstract data types, what do queues ...
0
votes
0answers
25 views

Are fat trees dynamic or static network topologies?

Is a fat tree topology a dynamic or static network topology? Because as far as I understood a binary tree is a static topology, but we have different stages for a fat tree. Are all multistage networks ...
0
votes
1answer
52 views

Does modern type theory include specifications and implementations?

Good programming practice distinguishes between specification (at the API level) and implementation. I would have thought that this same distinction would be found in type theory. Perhaps I just don't ...