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

learn more… | top users | synonyms

1
vote
2answers
37 views

Is there a name for graphs which contain oriented and non-oriented edges?

Is there a name for graphs which contain oriented and non-oriented edges? I couldn't find on the internet if there exist a specific name for such graphs.
7
votes
2answers
118 views

If O(log n) vs O(n) is exponential what is O(1) vs O(n)?

If one refers to using an O(log n) instead of an O(n) algorithm as an exponential speedup, how would one refer the speedup ...
3
votes
2answers
93 views

What is running time of an algorithm?

What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the ...
1
vote
2answers
42 views

Turing machine states, lost in the jungle

There is a lengthy discussion going on at the English Language & Usage StackExchange site suggesting various synonyms for dead code, and it got me wondering about an angle that wasn't covered -- ...
-1
votes
3answers
89 views

Terminology for trees

In a tree, I want to refer to a particular child of a node, the child of this child, the child of this child of this child, and then the child of this child of this child of this child. For instance, ...
57
votes
1answer
6k views

What does the “Lambda” in “Lambda calculus” stand for?

I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from. Can anyone explain the origins of the ...
0
votes
2answers
42 views

What is an upright rectangle?

What is an upright rectangle? I came across the phrase in my homework - "The bounding box of a set of S points is the smallest upright rectangle containing S. Describe and analyze an algorithm to ...
-1
votes
1answer
29 views

How is a procedure application a control structure?

In scheme, a procedure application is considered as a control structure. Why is this?
2
votes
2answers
81 views

What defines a tool as a “compiler”

I've been trying to figure out what technically makes a tool or program a compiler. For example, I know that gcc will compile source code to object files or assembly, hence transforming a ...
23
votes
4answers
4k views

What exactly (and precisely) is “hash?”

I have heard the word "hash" being used in different contexts (all within the world of computing) with different meanings. For example, in the book Learn Python the Hard Way, on the chapter of ...
4
votes
0answers
38 views

Proper pronunciation of “Aho-Corasick?”

Tomorrow I'm going to be teaching a class on Aho-Corasick string matching. I'm pretty sure I know how to pronounce Margaret Corasick's name, but I don't actually know the proper pronunciation of ...
1
vote
1answer
45 views

What is the name of the word problem for free groups under straight line program encoding?

I believe that the word problem is the problem to decide whether two different expressions denote the same element of a suitably defined algebraic structure. For simplicity, let us focus on free ...
-4
votes
1answer
44 views

How do you call this typical file name order? [closed]

log1.gz log10.gz log100.gz log101.gz log102.gz log103.gz
10
votes
3answers
2k views

What does Θ(1) memory mean?

I have the definition of an in-situ algorithm from the professor, but I don't understand it. In-situ algorithms refer to algorithms that operate with Θ(1) memory. What does that mean?
-1
votes
1answer
135 views

What is the difference between formal language, regular language and regular expression? [closed]

I want to know the difference between these three languages and it would be great if you would give some examples as well, thank you. :)
5
votes
1answer
72 views

How did each class of languages receive their name?

If we look at the Chomsky hierarchy, we see that there are four well-known classes of languages: regular languages, context-free languages, context-sensitive languages, and recursively enumerable ...
1
vote
0answers
50 views

Difference between capacity miss and conflict miss

Premise: Two types of cache miss: capacity miss, conflict miss\ Cache contains only 2 sets, SET 1 and SET 2 Problem: If data A maps to SET 1 and it doesn't exist in SET 1 while SET 1 is fully ...
1
vote
0answers
10 views

What is the term for the object to be identified in a pattern recognition problem?

What is the term for the object to be identified in a pattern recognition problem? So, for example, if one were matching a glyph expected to be an alphabetic letter to a set of templates, what is the ...
3
votes
1answer
29 views

How to correctly define the ratio of an approximation algorithm?

For a maximization problem $P$, I know that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|OPT|\ge |S| \ge \gamma\cdot|OPT|$ for $\gamma <1$ and $OPT$ the optimal ...
2
votes
1answer
29 views

What is a local inference system?

A inference system is a set of rules that can be used to prove something in some formal model. I understand that. But what does it mean to a inference system to be local? For instance, in the page ...
1
vote
0answers
30 views

Clustering of matrices

I have a matrix of n lines and T columns, containing only 0's or 1's. I would like to make permutations of lines (and lines only) to make the largest submatrix of 1's possible (i.e. i want to find ...
1
vote
2answers
56 views

Why are Complexity Notations Called Asymptotic?

Why do we use the term "asymptotic" in complexity. Although I know what an asymptote is, but what is an asymptote doing here?
5
votes
1answer
85 views

Difference between “sort” and “universe”

A very basic question. As title, what is the difference between "sort" and "universe" in type theory? Are they interchangable? Or are there only finite number of sorts, but infinite universes?
3
votes
1answer
44 views

The language of Logical Theory as Metalanguage

I am reading the Handbook of Satisfiability, and in Chapter 1 (History of Satisfiability), I found the following statement: Moreover, necessary and possible are predicates of the metalanguage ...
4
votes
1answer
58 views

What are predicates of a sentence?

I am reading Handbook of Satisfiability in which they say: An algebraic structure, or simply structure, consists of a non-empty set of objects existing in the world $w$, called the domain and ...
0
votes
0answers
62 views

Is there any difference between information architecture and information structure in case of web apps?

In the course of Web Engineering, the course teacher said in the class of Information Design that site map has 4 main kinds. Linear Layout Hierarchical Layout Grid / Matrix Type Structure Network / ...
2
votes
1answer
36 views

What is a good example to illustrate the difference between isomorphic and homomorphic representations?

I am learning about "knowledge representation" in my intro to AI course and one of the key ideas has to do with isomorphic vs homomorphic representations. The examples I find when I google around are ...
4
votes
0answers
32 views

What is the difference between Cased-based Reasoning and Rule-based reasoning?

As stated here, Rule-based Reasoning systems are considered to be "old style" AI that uses rules prepared by humans - as opposed to Neural Networks where machine recognizes pattern i.e. acquires new ...
1
vote
2answers
52 views

How do you express the theorem statement about unsuccessful search on average-case for unsuccessful searches in hashing with quantifiers?

I was reading CLRS and in theorem 11.1 it states: In a hash table in which collisions are resolved by chaining, an unsuccessful search takes average-case time $\Theta( 1 + \alpha )$, under the ...
2
votes
1answer
59 views

What is the difference between modulo and modulus?

Throughout my education in computer science, I feel like I've heard the terms "modulo" and "modulus" used interchangeably. It looks like even Wikipedia claims that "modulo" is "sometimes called ...
1
vote
1answer
36 views

Revisiting Fixed Point: What does it mean in the world of computer science?

A while ago I asked Fixed point, what does it mean in the world of computer science? While the answers did help me to understand what Fixed point meant, the answers left me in a murky world when ever ...
1
vote
1answer
86 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: ...
-2
votes
1answer
57 views

Difference between system calls, system call interface and API? [closed]

Lets take POSIX, whats the difference between POSIX API, libc and actual system calls?
5
votes
1answer
403 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
67 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
56 views
3
votes
1answer
18 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
78 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
51 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
64 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 ...
15
votes
4answers
709 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
99 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 ...
5
votes
1answer
293 views
2
votes
2answers
267 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
48 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
43 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 ...
1
vote
1answer
45 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
59 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
300 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 ...