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

learn more… | top users | synonyms

3
votes
3answers
47 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
18 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
56 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
219 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
32 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
20 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
62 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
110 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
31 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
40 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
14 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
79 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
36 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
63 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
79 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
26 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
26 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
34 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
77 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
57 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
62 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
61 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
68 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
137 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
77 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
25 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
46 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
204 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
21 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
50 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 ...
1
vote
1answer
83 views

Semantic Code Comparison

Consider two codes that do the same thing, in the same time and memory order, But they don't do it exactly the same way. Is there any Idea for a program to declare those codes as the same? For ...
0
votes
1answer
155 views

What could 'two characters are terminals' mean?

In the context of this statement, what does 'a & b are terminals' mean? Stacks and queues can be used for determining whether a particular input string is in the language or not. L = ...
2
votes
1answer
31 views

Can A still be a key if two tuples are the same

I am studying database functional dependency. It says if A can functionally determine all other attributes, it is considered to be a key. What if 2 tuples are exactly the same, can we still say A is ...
1
vote
1answer
60 views

Name for class of algorithms preserving accuracy/confidence

I am considering the following class of algorithms: The algorithm has access to some probabilistic oracle (procedure) $f$ in addition to input. The answer of procedure $f$ (we may assume it is ...
0
votes
1answer
53 views

State of variables in dynammic programming [closed]

I would like to know what a state variable is in simple words, and I need to give a lecture about it. I have chosen the Longest Common Subsequence problem I found a similar question but it has no ...
1
vote
2answers
57 views

Are neural networks dynamical systems?

Dynamical systems are those whose evolution can be described by a rule, evolves with time and is deterministic. In this context can I say that Neural networks have a rule of evolution which is the ...
1
vote
2answers
116 views

What is the term for this set

I have a set of related data/objects for which, when undergoing some algorithm, there should be only one valid match. Is there a unique term for this type of set? A common practical use case would be ...
3
votes
1answer
96 views

Conceptual question about entropy and information

Shannon's entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that ...
2
votes
1answer
50 views

Is there a limit on the length of queries for the oracle?

Consider the class $L^A$ which contains all the languages that are decided by a deterministic Turing Machine that uses $O(log(n))$ space and that can make queries to an oracle that decides $A$. My ...
5
votes
1answer
52 views

What is $Prop$ in the calculus of constructions?

I'm looking at the Calculus of Constructions and its place in the Lambda Cube. If I understand correctly, each axis of the cube can be thought of as adding another operation involving types to the ...
7
votes
2answers
111 views

Combinatory interpretation of lambda calculus

According to Peter Selinger, The Lambda Calculus is Algebraic (PDF). Early in this article he says: The combinatory interpretation of the lambda calculus is known to be imperfect, because it ...
2
votes
0answers
40 views

What is a semantic cognitive map

Based on: J. P. Carvalho, "On the Semantics and the Use of Fuzzy Cognitive Maps in Social Sciences" (WCCI, 2010 -- PDF) and Richard Dagan's web page Cognitive Mapping. A cognitive map consists of ...
5
votes
1answer
92 views

Difference between hypervisor and exokernel

An hypervisor (1st type) is a software that creates and run virtual machines, managing guest's operative systems's requests to the hardware. An exokernel is an operative system kernel, that let's ...
2
votes
1answer
61 views

Use of Big-O Notation: Size of Input vs Input

It is my understanding that, when one is describing time complexity with $\mathcal{O}$, $\mathcal{\Theta}$, and $\mathcal{\Omega}$, one must be careful to provide expressions with regards to the size ...
-2
votes
1answer
45 views

Generative grammars and analytic grammars?

What are a generative grammar and an analytic grammar? How are they different from a formal grammar? Is the recursive definition of the language of a propositional calculus, a first order logic ...