Questions tagged [terminology]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
98 views

Explicit algorithms and algorithms involving unknowns

Let's assume the you have two algorithms for computing some single but complicated number (e.g., the Ramsey number $R(5,5)$). Both are provided as high-level, half-formal textbook descriptions. The ...
3
votes
1answer
65 views

What is $C_4$ + two “ears” called?

A graph with $C_3$ + 3 "ears" is called a net graph. In general, $C_n$ + $n$ pendant vertices are called sunlet graphs. Is there a name for 4-sunlet graph minus two pendant vertices?
3
votes
3answers
3k views

Is there any difference between Time Complexity and Running time?

Is time complexity and running time of the program/algorithm one and the same thing? Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that ...
2
votes
1answer
210 views

Why is it called 'throwing' an exception?

I'm just wondering where the phrase "throwing" an exception came from. I understand "raising" an exception but I'm wondering if "throwing" has a reason or meaning behind it?
1
vote
2answers
46 views

How are lookup tables described from the perspective of complexity theory?

Lookup tables can convert a piece of computational time into space. I remember that it was a part of a complexity theory course, but I cannot recall how it's called in its terms. I know how to use ...
0
votes
0answers
25 views

What topics are related to “concept drift”?

The term "concept drift" specifically relates to a model changing over time. However, a similar phenomenon may manifest in, e.g., spatial data, where a topographical model changes behavior at a land/...
2
votes
0answers
150 views

Term for weak head normal forms that cannot be reduced in any environment

In my understanding, a lambda expression is a normal form (NF) when it has no redexes. For instance, $\lambda x.x$ is a NF, but $(\lambda x.x)y$ is not. A lambda expression is a weak head normal form (...
0
votes
0answers
517 views

What is the correct term for a probabilistically complete algorithm?

I'm wondering what the correct term for an algorithm that is probabilistically complete is. An algorithm is probabilistically complete if the probability of finding a solution, should a solution exist,...
1
vote
1answer
230 views

High Level Assemblers vs Compilers?

I'm reading the "Art of Assembly" 2nd Edition by Randall Hyde. In the book the author seems uses his own language called High Level Assembly (HLA). Coming from a C Background, I question how useful ...
2
votes
1answer
110 views

Do the classes $P$ and $NP$ include problems faster then polynomial?

I have being reading up on complexity classes (in Rieffel & Polak, 2011; pg149). I am slightly confused about something. Does for example $P$ (DTime($n^k$)) include all problems that can be solved ...
0
votes
1answer
32 views

A Question about what it means to Compare two Vectors

Please consider the following question: Given an integer m by n matrix A and an integer m-vector b, the 0-1 integer programming problem asks whether there exists an integer n-vector x with elements in ...
0
votes
1answer
27 views

terminology: half adders, full adders

I'm very confused about the reasoning for these circuits being called 'full adders' and 'half adders' I've read before that 'half adders' are called so, because two of them make up a 'full adder', ...
1
vote
2answers
572 views

Correct term for a priority queue with unique elements

Is there a standard term for a priority queue which can only hold a single occurrence of any element? This would be a priority queue for which operations such as "raise the priority of element ...
3
votes
1answer
966 views

What are the primal and dual planes in the context of the point-line duality?

In computational geometry, we can define a duality between points and lines. The line is the primal (or dual) object of a point, or a point is the primal (or dual) object of a line. However, the exact ...
1
vote
1answer
350 views

Bisimilarity and Trace Equivalence in Labelled Transition Systems

I'm a bit confused regarding the relation between trace equivalence and bisimilarity. These lecture notes I found and a few others documents I've read state that "if an LTS is deterministic then two ...
1
vote
2answers
83 views

Definition of InLeft and InRight

So in reading I have come across the terms "InLeft" and "InRight" and I am unable to find a concrete definition for it. I have found it used in the specification for COQ, and in some notes on ...
4
votes
1answer
361 views

What is the name for a function's “return arity”?

The number of parameters a function has (and thus the number of arguments it can take) is known as arity. What is the name for the number of values a function returns? I'm not asking for the "size" of ...
1
vote
2answers
72 views

What mathematical terminology exists for “embellished trees”?

I'm looking for some pointers on proper mathematical (FP?, category-theory?) terminology. My apologies if the below is somewhat imprecise; I suppose the precision is precisely what I'm looking for in ...
2
votes
0answers
888 views

Latency and Throughput Bounds

Say that I have a superscalar processor and I am given the latency, issue and capacity (in clock cycles) for different instructions. What is the general formula for latency bound and throughput bound?...
6
votes
3answers
816 views

Why is the set for which a decision problem is true called a “language”?

When we have a decision problem, " does $f(x)=1$ hold?", we call the set of strings $x$ for which the answer is yes a "language". Why this strange terminology?
1
vote
0answers
322 views

What's elementary operation in Computer science?

What do Computer Science mean when they use the Term Elementary Operations?
1
vote
0answers
22 views

Is there a term for mixing deferred and eager evaluation?

I've written a model which utilises deferred evaluation for many aspects of its feature but in one instance of its use it is mixed with threaded eager evaluation for things that are expected to be ...
2
votes
2answers
97 views

What is the name for the comparison used in C's memcmp?

The C memcmp function (and strcmp) does a comparison similar to the function below for comparing integers: ...
6
votes
1answer
588 views

What does the “big O complexity” of a function mean?

What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?
2
votes
1answer
70 views

What do we call a greedy algorithm that tracks the best $n > 1$ solutions?

A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima. To avoid this problem, we may keep track of the best $n > 1$ ...
12
votes
5answers
3k views

Why does soundness imply consistency?

I was reading the question Consistency and completeness imply soundness? and the first statement in it says: I understand that soundness implies consistency. Which I was quite puzzled about ...
83
votes
11answers
24k views

Why is the unit of image size not Pixel²?

If you calculate the area of a rectangle, you just multiply the height and the width and get back the unit squared. Example: 5cm * 10cm = 50cm² In contrast, if you calculate the size of an image, you ...
2
votes
1answer
159 views

Finite Automata: Final vs Accepting States

What is the difference between a final and accepting state when addressing an automaton? As I understand it, a final state is depicted (traditionally) with a double circle, and apparently so is an ...
1
vote
2answers
32 views

Not quite-infinitely expandable human-friendly naming system?

This may be a known problem, with known approaches, but I can't find the right way to search for it. I would like to name points along a line of unknown final length such that their name reflects ...
0
votes
1answer
308 views

What is the difference between a Standardization and a Specification?

While asking this question on "what exactly is standardization", I remebered that another related term that always came up while reading about C libraries was the term "specification". To avoid asking ...
0
votes
3answers
1k views

What is standardization in computer science?

I was reading about the differences standards and specifications for C. I understood that programming languages are usually stadardized and I learnt that there are different approches to ...
4
votes
1answer
2k views

What does synchronous and asynchronous mean in computer science?

Words synchronous and asynchronous can be met several times, in different contexts, when studying computer science. As an example : Synchronous and asynchronous circuits. Synchronous and asynchronous ...
1
vote
1answer
45 views

What is the computational complexity category of $T(n) = m^{\frac{n-1}{m}}$?

I'm analyzing the computational complexity of an algorithm whose input size is $n$. Finally, I've ended up with $T(n) = {m^\frac{n-1}{m}}$ where $m$ is a constant. Can one explain the type name ...
2
votes
1answer
1k views

What is a ridge - Hill climbing

I do not understand what is a ridge for hill climbing. The definition I found is a place where all points appear like a maximum, but how is that different than a plateau?
0
votes
1answer
254 views

What us difference between distributed computing and workgroup computing?

According to the definition, distributed computing means to distributed a problem among different users while workgroup computing means to work on a problem by different users. So what's the ...
0
votes
1answer
3k views

Why must a Primary Index be sparse?

Reading Fundamentals of Database Systems 7th Edition, on Page 603, it says, Indexes can also be characterized as dense or sparse. A dense index has an index entry for every search key value (and ...
5
votes
5answers
2k views

Why call it 'Time Complexity'?

P.S. I have added the tag 'history', if there is any historical connotation. Also, I found this question What is running time of an algorithm? but I am not satisfied with answers.
2
votes
0answers
42 views

What is cyclomatic complexity and how relevant it is today? [closed]

I have read that cyclomatic complexity is widely used, but critique on it exists claimed that it is based on poor theoretical foundations and an inadequate model of software development. I have read ...
0
votes
2answers
717 views

What does “effective enumeration” in Turing machines mean?

what is meant by EFFECTIVE ENUMERATION i have comes across this word when I was reading about enumerators for Turing machines is it same as LEXICOGRAPHIC ORDER? so effective enumeration is possible ...
3
votes
2answers
265 views

What is “Containment order”? Could I get a friendly explanation?

Reading the Wikipedia page was a little dense for me. Can anyone offer a friendly explanation of what this means? It sounds like it saying that if you have two ordered collections, if they are "...
6
votes
1answer
345 views

What does “local” mean?

I study graph theory on my own using Diestel's Graph Theory book (with Algorithmic graph theory in mind). I don't understand what local property, global property, locality mean given a graph $G$. ...
6
votes
1answer
462 views

What is static complexity?

Definition : Kolmogorov complexity is a static complexity measure that captures the difficulty of describing a string. For example, the string consisting of three million zeroes can be described with ...
8
votes
2answers
3k views

How do we define a tree in a directed graph?

I am trying to solve the exercise 3.3 in Approximation Algorithms by Vazirani, pg 34. It states 3.3 Give an approximation factor preserving reduction from the set cover problem to the following ...
1
vote
0answers
138 views

What is the name for the recursion scheme in which data flows top-down exclusively?

This is a question that is in a sense a follow-up of a question I asked earlier, and which was answered. In that question, the answer to "in which recursion scheme does data only flow bottom up, and ...
0
votes
2answers
289 views

Definition of “idempotence” of a function?

Currently there are two things that may change between invocations of a function: the return value, and the external states. I understand that if the external states changes, the function is not ...
6
votes
1answer
721 views

Reception of numerical infinities

A group of computer scientists associated with numerical analyst Yaroslav Sergeyev have published numerous publications recently on a scheme proposed by Sergeyev that uses terms like Infinity Computer,...
0
votes
0answers
38 views

Are the terms “Language Implementation”, “Runtime” and “Virtual Machine” synonymous?

To describe the implementation of a dynamic programming language, I have seen the terms "Runtime" (e.g. Security transparency in the Python runtime), "Virtual Machine" (Python Virtual Machine (PVM), ...
1
vote
1answer
113 views

size of a variable [closed]

I'm a beginner. I would like to know if the size of a variable (and generally speaking of a storage space) is: Its capacity (the amount of data that can be put in it). The amount of data it contains
0
votes
1answer
44 views

Is there a concept of information that distinguishes between “computed” and “non-computed” information?

I always tend to think of information as follows: If we have an information set $I$, and it is possible to derive from $I$ another information set $X$, then $I$ really contained $X$ all along, and we ...
1
vote
2answers
124 views

Formal names of nested functions

I have a nested function as follow: ...

1 2 3
4
5
22