# Questions tagged [terminology]

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

1,052 questions
Filter by
Sorted by
Tagged with
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 ...
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?
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 ...
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?
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 ...
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/...
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 (...
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,...
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 ...
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 ...
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 ...
27 views

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', ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?...
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?
322 views

### What's elementary operation in Computer science?

What do Computer Science mean when they use the Term Elementary Operations?
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 ...
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: ...
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?
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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.
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 ...
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 ...
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 "...
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$. ...
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 ...
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 ...
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 ...
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 ...
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,...
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), ...
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
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 ...