9
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.
7
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 randomized pivoting rules, due to Friedmann, Hansen, and Zwick. The lower bounds rely on lower bounds for policy iteration algorithms for parity games, which are ...
6
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 $A^n$. For example, the Kannan-Lipton Orbit Problem asks, given two vectors $s,t\in \mathbb Q^d$, whether there exists $n$ such that $A^ns=t$.
These types of ...
4
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 transformation semigroup, your question is about finitely generated semigroups that are quotients of the semigroup $S_n$ with presentation
$$
\langle a_1, \ldots, a_n \mid ...
2
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 classes. Some of this work goes back to Bellantoni & Cook. More recently, the work of Ugo Dal Lago comes to mind.
1
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
$$f(f(c)) = f(c) = c.$$
A set of fixed-points is often called a fixed set.
In your scenario, the output of $f$, or
image of $f$, is
a fixed set itself.
Only top voted, non community-wiki answers of a minimum length are eligible
