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

learn more… | top users | synonyms

0
votes
1answer
34 views

What is a stateful computation?

I am reading about a specific field of probabilistic programming, and trying to understand what the term "stateful computation" means. See: ...
-1
votes
1answer
19 views

Difference between system calls, system call interface and API?

Lets take POSIX, whats the difference between POSIX API, libc and actual system calls?
3
votes
1answer
362 views

Is something more than Turing complete Turing complete?

In complexity theory, we do not call a decision problem that is not in NP "NP-complete". But in computability, do we call a machine model "Turing complete" if it can compute functions which Turing ...
4
votes
1answer
56 views

What does Harper mean by “class”?

I've been teaching myself type theory on and off over the past couple years. I've reach large sections of Pierce's Types and Programming Languages and Harper's Foundations of Programming Languages, ...
0
votes
1answer
49 views
3
votes
1answer
12 views

Informed search with a lower-bound heuristic?

I am well aware of informed graph / tree search strategies for optimal solutions when one has an admissible heuristic - i.e. one that never overestimates the minimum cost from a node to any goal ...
1
vote
1answer
67 views

What do you call a function from symbols of alphabet to languages?

Speaking of context-free (and maybe regular? or just any?) languages, what do you call a function defined as follows: Let $\Sigma$ be the alphabet of $L$, $\forall \sigma \in \Sigma: f(\sigma) = L'$, ...
1
vote
2answers
48 views

Computer cache - data removing

I am programming CPU cache simulator and I am supposed to implement removing of entries. I will not use LRU but just random. I am not really clear, when should I call the removing function? When ...
1
vote
1answer
48 views

Algorithmic Composition: generative vs transformative algorith

What's the difference between generative and transformative algorithms in relation to algorithmic composition of music? As I understand the basic idea of the algorithms themselves, generative uses ...
13
votes
4answers
651 views

Why are computable functions also called recursive functions?

In computability theory, computable functions are also called recursive functions. At least at first sight, they do not have anything in common with what you call "recursive" in day-to-day programming ...
4
votes
2answers
1k views

What would we call this datastructure?

Suppose we have a datastructure that is a list containing elements that are either a leaf or another layer of the datastructure (recursively defined). What would we call this? It isn't a tree, since ...
1
vote
1answer
96 views

What does the term “Finite” stands for in Finite State Machines?

Do we consider Pushdown Automata, Turing Machines in Finite State Machines? If we don't, then what does the term "Finite" stands for in Finite state machines, as PDAs & TMs are also defined to ...
4
votes
1answer
124 views
1
vote
2answers
63 views

What is the difference between object detection, semantic segmentation and localization?

I've read those words in quite a lot of publications and I would like to have some nice definitions for those terms which make it clear what the difference between object detection vs semantic ...
0
votes
1answer
47 views

Are parser combinators equivalent to scannerless parsing?

From what I can see, parser combinators are equivalent to scannerless parsing. I do not see this stated in implementations of scannerless parsing page, nor in the parsing combinators page, neither in ...
-2
votes
1answer
42 views

All regular languages are context-free so why does the terminology not reflect that? [closed]

Since Regular languages $\subset$ Context-free languages, then Regular languages are Context-free languages? Why is the terminology so different then? To me these seem like a totally different class ...
0
votes
0answers
36 views

In computer science, is there a term that describes a solution set that is guaranteed to contain the solution to a NP hard problem?

Suppose that a NP hard problem involves finding a set $A$, and that there exists a polynomial time algorithm that is able to find a smallest set $B$ such that $A \subset B$. Occasionally, we might be ...
1
vote
1answer
31 views

What's this type of semantic analysis called in NLP?

I'm speculating that this is very much known in NLP, but as I've not studied NLP, I don't know what concepts are related to this: Basically I have entities that are connected by some strings. I ...
4
votes
2answers
55 views

Anatomy of a production rule

Production is said to be of the form $u \to v$. I want to know if you distinguish $u$ from $v$ giving them some distinguishing names, like LHS/RHS or something alike.
3
votes
6answers
236 views

Parallel vs Distributed Algorithms

Let me clear first that I am not asking about parallel (data/task) or distributed computing architecture. A lot had been discussed here. I am just asking a plain theoretical question. What is core ...
6
votes
0answers
47 views

Is THEADS the same as FIRST?

I'm reading the paper "A Practical General Method for Constructing LR(k) Parsers" by David Pager, and it contains the following paragraph: We will first of all briefly review the LR(1) parsing and ...
5
votes
3answers
78 views

Terminology needed for the computational solution to the Rubik's Cube

I apologize if this question is out of the guidelines of this forum. If it is please let me know and I will abstain from requesting definitions and terminology. Hello! I am currently writing a ...
0
votes
1answer
33 views

Terminology for Digitally Interpretting Environment

I am looking into coding a program that can Analyse an image and identify objects in that environment (incl their depth and contours/shape). What is the term for this? Is there a term or area of ...
1
vote
1answer
72 views

Is O(ln n) “exponentially faster” than O(n)?

I improved the complexity of an alogrithm from $O(n)$ to $O(\ln(n))$. Is it legitimate to call this an "exponential speedup" in a scientific publication? Usually I think going from NP to P when I hear ...
1
vote
2answers
31 views

What is monograph and digraph in keyboard optimization problem?

I have been working on Bangla keyboard optimization. I've taken this paper as a reference. In this paper they have introduce two terms monograph and digraph. But it is not clear how they have ...
0
votes
1answer
21 views

The symbolic differentiation of univariate expressions

I was reading "Doug McIlroy: McCarthy Presents Lisp" and the phrase "symbolic differentiation of univariate expressions" triggered a faint memory of a demonstration of differentiation done in haskell ...
-2
votes
2answers
35 views

Alternative for regular expression

Could the following be considered as an alternate regular expression for regex $a(aa)^*$? $a^k$ where $k$ is odd. Could the following be considered as an alternate regular expression for regex ...
2
votes
1answer
34 views

Why arrival process of packets at a switch is not a Poisson Process?

"Packet arrivals are not Poisson .... but some events are, such as web requests and new flow arrivals" I know since the network traffic is very bursty, they are not Poisson. But I am unable to ...
2
votes
1answer
75 views

What does it mean to fool a function?

In computer science papers, I see about the term 'fooling' a function. What does it mean to fool a function against a particular complexity class? Why is it important?
5
votes
3answers
70 views

What does it mean to be “independent of machine model”?

I have often heard people mention off-hand that the class $\mathsf{P}$ is "machine-independent", or "independent of machine model", or "invariant under change of machine model" - something to do with ...
4
votes
1answer
70 views

Variations of Greedy Algorithm

What is the definition of an "orthogonal greedy algorithm"? What is the definition of a "relaxed greedy algorithms"? Can you give an example to illustrate how these notions differ from ordinary ...
2
votes
1answer
36 views

Term for shifting work to idle machines

I am looking for a term here. A while ago, i was told about a network in which all the computers are connected in parallel, and when a computer is idle, the central server sends heavy cpu usage tasks ...
2
votes
0answers
40 views

Differences between programming model and programming paradigm?

What is the relation and difference between a programming model and a programming paradigm? (especially when talking about the programming model and the programming paradigm for a programming ...
0
votes
2answers
31 views

Is the program in secondary memory can be a process?

Let us consider the following scenario, The cpu started executing a program, which is in secondary memory with n lines of code, so, it brings m ( < n ) lines of code in to main memory and started ...
1
vote
1answer
17 views

Term for an approximation that becomes better as the problem grows

For a certain maximization problem, a "constant-factor approximation algorithm" is an algorithm that returns a solution with value at least $F\cdot \textrm{Max}$, where $F<1$ is some constant and ...
1
vote
2answers
20 views

What do you call a subtree covering a subset of contiguous leaves?

In the data structure field, what is the (best) term used to identify (designate) a subtree covering a subset of contiguous leaves?
2
votes
1answer
48 views

A model of computation vs an abstract machine

Wikipedia says A model of computation is a formal description of a particular type of computational process. The description often takes the form of an abstract machine that is meant to perform ...
1
vote
0answers
30 views

Computer Scientific term for languages outside the Logic Programming paradigm

Is there a term for languages, imperative, declarative, procedural, functional alike; a term describing the quality of functions being represented as a (reversible) relationship between inputs and ...
4
votes
5answers
661 views

Data structures as algorithms themselves

Can data structures be thought of as algorithms themselves? For example, I could implement a stack data structure that has certain non-functional characteristics. Is the separation between data ...
2
votes
1answer
68 views

Does proving a problem is in P typically mean it will eventually be practically solvable?

I'm currently reading Introduction to the Theory of Computation by Michael Sipser and in his section on time complexity, he tries to justify why theoretical computer scientists divide problems into P ...
1
vote
3answers
73 views

What's the difference between a “dead” and “empty” state?

In computational theory, I came across both deterministic and non-deterministic finite state machines but I heard someone said there are no dead states in deterministic machines. I thought dead and ...
2
votes
1answer
52 views

Why are states called locations in Timed Automata?

I started reading about timed automata lately. In the definition, they have locations instead of states as in automata theory. Can anyone explain why is this?
0
votes
1answer
81 views

What is the name of this code transformation that uses associativity of addition?

I am learning about compiler optimization technique and there is a technique that use associativity of addition to transform code. For example, consider the following expression: ...
-3
votes
1answer
101 views

Complement of a Language which is set of Turing Machine descriptions

If $L$ is the set of strings $\langle M\rangle$ such that $M$ accepts all strings of even length and does not accept any strings of odd length. What will be $\overline L$ ? a) set of strings ...
0
votes
1answer
61 views

What does the term maximum-bottleneck (s,t)-path in the context of maximum flow optimization?

I was reading the following notes on maximum flow and it said the term "maximum-bottleneck (s-t)-path" but I couldn't find were it precisely defined it, so I am left guessing what it means. I am ...
0
votes
2answers
195 views

Is word size, the size of a memory location? the size of the data bus? or the cpu register size?

Is word size, the size of a memory location? the size of the data bus? or the cpu register size? Suppose you have a computer, memory address #0 has byte AB memory address #1 has byte F3 memory ...
0
votes
0answers
21 views

What does detection stability mean?

I am reading the paper "A new approach to intrusion detection using Artificial Neural Networks and fuzzy clustering" by Gang Wang, Jinxing Hao, Jian Ma and Lihua Huang (Expert Systems with ...
9
votes
1answer
110 views

If $n^{\log n}$ is not polynomial or exponential, then what this function is called?

I just found this sentence on page 6 of Garey and Johnson's "Computers and Intractability". Any algorithm whose time complexity function cannot be so bounded is called an exponential time ...
3
votes
3answers
68 views

Computational problem - definition

How should I understand the definition of computational problem? A computational problem is a mathematical object representing a collection of questions that computers might be able to solve. ...
3
votes
1answer
36 views

Subgraph of an interprocedural control flow graph

Say I have the interprocedural control flow graph (ICFG) of a program. Now I am only interested in the control flow between two functions f1 and f2. What is the most straight-forward way to remove ...