9 votes
Accepted

Adjective for: algorithm that outputs its input if it is one of its outputs?

In mathematics we would say $f$ is an idempotent function. It's a widely known term and I suppose most TCS people should also recognize it.
Ilkka Törmä's user avatar
7 votes
Accepted

Terminology about computation and Finite algebra

Such algebras are called functionally complete. Also, what you call terms are actually called polynomials. In standard terminology, term operations have a more restricted definition that allows ...
Emil Jeřábek's user avatar
7 votes

Are there any intersections between Theory A and Theory B?

One cool example of work that straddles things that are typically considered theory A and things typically considered theory B are the lower bounds on the running time of the simplex algorithm with ...
Sasho Nikolov's user avatar
6 votes

Are there any intersections between Theory A and Theory B?

One example (from my research field) is analysis of dynamical systems: in a (linear) dynamical system, you are given a matrix $A\in {\mathbb Q}^{d\times d}$ and you reason about various properties of $...
Shaull's user avatar
  • 5,571
4 votes
Accepted

What is the name of this algorithm on direct acyclic graph?

Looks to me like some additional restrictions on a topological sort: https://en.m.wikipedia.org/wiki/Topological_sorting . Also git already supports this operation for instance git rev-list --topo-...
Max New's user avatar
  • 1,675
4 votes

Is there a notion of "sequential" idempotence?

Your question would probably fit better on MathsStackExchange, but here is an answer. I don't think there is any specific name for your definition. Since any semigroup is isomorphic to a ...
J.-E. Pin's user avatar
  • 4,831
4 votes

What is First-Order Rewritable (and FO-Query)?

Here is another attempt at a more comprehensive answer. Your question already contains the formal definition of FO-rewritability, which at its core says that you can reduce a query answering problem: ...
mak's user avatar
  • 504
2 votes

What is the etiquette of naming concepts after people?

It is best to spend some time researching to ensure that you associate the correct person with the idea and mention related ideas by others. You wouldn't want a misnomer to be called a Squark - like ...
Rob's user avatar
  • 121
2 votes

Are there any intersections between Theory A and Theory B?

As far as I understand it, linear logic and "implicit complexity theory" use tools that are often found in Theory B (type theory, theory of programming languages, etc.) to capture and study complexity ...
Joshua Grochow's user avatar
1 vote
Accepted

Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?

Yes! But I can see why it is confusing. A strongly explicit graph family $\{G_n = (V_n,E_n)\}$ (parameterized e.g. by number of vertices $n$) is described by an efficient ($\mathrm{polylog}(n)$ time) ...
smapers's user avatar
  • 849
1 vote

Adjective for: algorithm that outputs its input if it is one of its outputs?

Ilkka Törmä has already given the answer that $f$ is an idempotent function. You might want to be aware of the concept of fixed-points. A point $c$ is a fixed-point for $f$ if $f(c) = c$, and hence ...
Pål GD's user avatar
  • 550
1 vote
Accepted

Constraint terminology

This is not clear from your question, but I am going to assume that the groups are disjoint. I.e. $C = \bigcup_i C_i$ and $C_i \cap C_j = \emptyset$ for every $i \neq j$. Then the collection of sets $\...
Sasho Nikolov's user avatar
1 vote

Constraint terminology

To be clear that I understand the context, I'm going to first reproduce you situation worded differently. Consider a sequence of sets, $C_i$, and a target function, $f$. Let $\cup C_i=C$. We wish ...
Stella Biderman's user avatar
1 vote

what does "lifting" mean?

There is also Hensel lifting in modular arithmetic, that allows you to relate roots of a polynomial over a ring of integers modulo prime $p$ to roots of the same polynomial over integers modulo higher ...
Martin Schwarz's user avatar
1 vote

What is First-Order Rewritable (and FO-Query)?

As a complement to Janoma's answer above: it's 'very good'--- from the point of view of implementation --- because given a FO-rewritable language, we can use the powerful engines (for evaluating ...
Julio Lemos's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible