# Questions tagged [terminology]

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

103 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
143 views

### Complexity class for probabilistic approximation algorithms with bounded error

What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ...
736 views

### Turing Machine-Like Formalism for The Actor Model

Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done. The Actor Model is sometimes mentioned as a more powerful computational-...
71 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 ...
87 views

### What is 2g-precedence?

I am currently reading a couple of papers about event processing. In the context of ordering events, "2g-precedence" is frequently mentioned. I don't know what it is, and I cannot find much ...
157 views

### Has there been any attempt to systematically categorize programming puzzles?

Has there been any attempt to systematically categorize programming puzzles? I notice that some problems are similar to one another, or have analogous methods of solution. I would think there must be ...
238 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 ...
198 views

### Decomposing an Algorithm into Local Transformations/Perturbations

Is it common to try to improve an algorithm by decomposing its action on a topological piece of data (e.g. graphs, geometric data) into a series of steps, each of which only makes a local change/...
75 views

### Understanding a paper on polynomial recursion in all finite types

So I wasn't sure weather or not this counted as "research level" or not but I figured it wasn't so I decided to post it here. There is a paper by S. Bellantoni et al. called "Higher ...
59 views

### Words of the same length in a language

Let $L\subseteq\Sigma^*$ be a language, where $\Sigma$ is a set, and let $n\in\mathbb N$. I am wondering if there is some good terminology for $L\cap\Sigma^n$. Of course I could say "the set of ...
65 views

### What's the meaning of linguistics?

In the programming language theory world, there are two important terminologies, i.e syntax, and semantics. I can understand these two terminologies: syntax is about sentence's structure (e.g. a valid ...
981 views

### Backtracking vs Branch-and-Bound

I'm getting a bit confused about the three terms and their differences: Depth-First-Search (DFS), Backtracking, and Branch-and-Bound. What confuses me: Stack Overflow: Difference between '...
27 views

### Complementary of graph invariant

Graph invariant is a property that holds for two isomorphic graphs. For example, degree sequence is graph invariant. We can write $d(G) \ne d(G') \Rightarrow G \ncong G'$, although $d(G) = d(G')$ ...
152 views

### Name for function in big O but not in little o?

Let $f(n) = O(g(n))$, but not $f(n) = o(g(n))$. That's a nice property, because it means that we cannot replace $g(n)$ with a substantially smaller function. Is there a name for this choice of $g(n)$? ...
161 views

### Is "expert system" now an obsolete/unpopular term?

While doing research on expert systems, I notice that it is rare to see this term used in the last 20 years. For example, a recent paper was: Wang, Hao, Naiyan Wang, and Dit-Yan Yeung. "Collaborative ...
1k views

### "Data-race free" programs

In section 6.3 of the paper Causal memory: definitions, implementations, and programming, the authors define "data-race free" as follows: Program $\Pi$ is data-race free if, for all ...
661 views

### λ-Calculus extensions: meaning of extension symbols

When working with λ-Calculus I see lots of extensions that use other symbols such as ∀ <:Top {} ←, which are from "Types and Programming Languages" (WorldCat) by Benjamin C. Pierce. ...
1k views

### what is the name for the space between the leaves of a tree

I am trying to write a data-type not for a tree, but for the spaces in between the leaves of thee tree. In number theory (a part of math) this is known as a topograph does it have a name in CS?
29 views

### Given a vertex in a digraph, is there a standard term for (the vertices reachable from it) union (the vertices reaching it)?

Question in title. Looking for whether there is a term that is, if not widely understood, at least citeable to a source. This is equivalent to asking for the set of nodes that are comparable to the ...
26 views

### What is tag-only forced cache inclusion called?

Is there a commonly accepted term for caches that are guaranteed inclusive with respect to tags but not data? Inclusion can be helpful to simplify cache coherence, for which use only tags need to be ...
18 views

### Is there a more commonly-used term for "multi-pivoting"?

Consider the following computational problem (or rather, task): Given: An array of $A$ of (not necessarily distinct) elements from a fully-ordered finite domain An ordered sequence pivot ...
174 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 (...
1k 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?...
52 views

### Formal name of the product of product type

What is the formal name in type theory of the operation that creates a "matrix of types" from product types (such as std::tuple in C++)? For example if we consider ...
618 views

### How to objectively quantify the simplicity of an algorithm?

I often ask for a "simple" algorithm that solves some problem and I realized that, almost aways, the answerers's notions of simplicity doesn't match mine's. Often, for example, I notice people using ...
23 views

### In what sense do we mean 'distributed' when talking about a distributed representation of words?

In machine learning literature, when handling words or text inputs, the strings are often mapped onto a vector space using techniques such as word2vec. The terminology in this is that the individual ...
29 views

### Terminology for non-game theoretic techniques

When solving an adversarial problem there are two basic approaches: one that takes into account the thinking process of both sides, and as opposed to that the non-psychological computations. For ...
677 views

### Black box terminology

Can we use the term "black box" to speak about an algorithm which has a polynomial complexity but for which we don't know exactly how are made the calculations? In fact I would like to explain that ...
110 views

### What is the difference between the research area of "ad hoc networks" and "device-to-device communication"?

I wonder what "device-to-device communication" (from a research perspective) covers what "ad hoc networks" don't. To the context of this question: I am reviewing papers which deal with "device-to-...
334 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 ...
502 views

### What is the difference between "objective function", "error function", "criterion function" and "cost function" in the context of neural networks?

The title says it all: I have seen three functions so far, that seem to be the same / similar: error function criterion function cost function objective function I am currently working on ...
207 views

### Is there a prefered name for the “effective access time” formula?

Any CS class about caches will at some point address this classical formula (or a variant of it) Effective_access_time = hit_time + miss_penalty * miss_rate My ...
251 views

### Difference between fully-reduced BDD and quasi-reduced BDD

I am trying to figure out difference between fully- and quasi-reduced BDDs. I have read a lot of material but still it is not very clear. As I am trying to figure out the quasi reduced version for ...
81 views

### Does a function distribute over lists or does it commute with them?

Assume that we have an operation $f$ such that $$f([a_0,\ldots, a_n])= [f(a_0),\ldots,f(a_n)]$$ Do we say that $f$ distributes over lits or do we say it commutes with lists? Which one is the ...
45 views

### Mersenne twister middle word

In some literature, as well as in Wikipedia, the middle term parameter m of Mersenne twister is called "number of parallel sequences". Why? What is meant here by "parallel sequences"?
18 views

### Does this Hamming-like algorithm for solving a permutation of an address space have a name?

I'm working on reverse engineering the bit stream format of an FPGA, in particular regarding the address translation of the BRAM (block RAM), but the algorithm could in general be used for any ...
26 views

### Correct terminology for $P1;P2$?

This question is about the correct terminology. Let $P1$ and $P2$ be two LOOP programs. Then $P1;P2$ is also a LOOP program, which executes $P1$ and then executes $P2$. Would this be called ...
27 views

### Calculus for Communicating Systems vs. Calculus of Communicating Systems

Robin Milner uses both terms: Calculus for Communicating Systems and Calculus of Communicating Systems and, AFAIK, writes CCS for both. Is there any difference between the two? Is there a difference ...
25 views

### Origin of GUI terminology

I'm wondering where the GUI terminology like modal dialogue comes from. Who first used these terms? Is there a paper or a book, or was it just sw?
71 views

### What are precisely computational effects?

I'm really confused with definition of computational effects. What I knew and understood about computational effect were only that they're impure computation, but someone noticed me that computational ...
36 views

### Meaning of "uniformly computably enumerable in m"

Nies, in Computability and Randomness, p. 6, defines "uniformly computably enumerable": A sequence of sets $(S_e)_{e\in\mathbb{N}}$ such that $\{\langle e,x \rangle : x \in S_e \}$ is c.e. is ...
505 views

### What is memory model in computer organization?

I'm new to Computer Organization and even to this community. I didn't find anything which was simple, clear and up to the point. Any examples supporting the discussion is appreciated. I'm not looking ...
14 views

### Is an error-correcting code where the parity symbols are interleaved with the data symbols considered systematic?

According to the Wikipedia entry, a systematic code is one in which the input data is embedded in the encoded output. Conversely, in a non-systematic code the output does not contain the input ...
85 views

### Terminology: Difference between decision variables, features and attributes?

Could there be a difference between the words "feature", "attribute", and "decision variable" when used in the same paper? The one I am specifically thinking about is about an optimization method for ...
61 views

### What is this weird gate?

This came from a picture of something that I'm supposed to make, and I can't find it in the program I'm supposed to use (LogicWorks). It looks like it 'not's only one of its inputs, but that doesn't ...
19 views

### A term for a set of vertices with a small set of neighbors

Given a graph $G(V,E)$ ans a subset $S\subseteq V$, define $N(S) =$ the set of neighbors of $S$. Is there a standard term for a subset $S\subseteq V$ for which $|N(S)|\leq |S|$? Is there a standard ...
646 views

### Which AC-3 algorithm is being used here?

This is the illustration of the AC-3 algorithm for four queens from exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem by Md. Ahsan Ayub, Kazi A Kalpoma,...
167 views

### Do SLR(1) parsers have lookahead?

The SLR(1) parses AFAIK does not have any lookahead with it then why do we write it as SLR(1) and not as SLR(0). The thing about parsers which I read online taught me that if it's LR(K) then K ...
353 views

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

What do Computer Science mean when they use the Term Elementary Operations?