17
votes
Accepted
Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs
I'm not sure, but you might be talking about what has been termed incremental computation.
The key idea behind incremental computation is to program in a way such that the program responds to input ...
- 11.3k
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.
- 661
8
votes
Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs
Some of the very early work on complexity theory used a sequential time model -- that is, rather than studying the worst-case runtime of the TM that can produce the correct output on an arbitrary ...
- 2,383
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 ...
- 18.1k
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 ...
- 16.5k
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 $...
- 5,521
6
votes
Accepted
On partitioning a collection into equivalence classes
See the paper
Varunkumar Jayapaul, J. Ian Munro, Venkatesh Raman, Srinivasa Rao Satti (2015), "Sorting and Selection with Equality Comparisons",
Proc. WADS 2015, LNCS 9214, pp. 434–445, doi:10.1007/...
- 50.8k
6
votes
Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs
It's difficult to know what you mean because you're staying at a level that's so high that there's nothing interesting. Specific cases could be very interesting, but the basic idea that having ...
5
votes
Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs
You seem to be asking about incremental computation.
In general, it takes the following form: we have a function $f$, which is expensive to compute. We have computed $f(x)$ for a single input $x$. ...
- 11.6k
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-...
- 1,638
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 ...
- 4,761
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:
...
- 494
4
votes
Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs
This is basically what dynamic data structures and streaming algorithms are about. A few links, off the top of my Google:
High performance data structure for streaming graphs
Mihai Patrascu's thesis
...
- 36.7k
4
votes
Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs
Many times, we can use Linearization of a function to approximate values near a point to reasonable accuracy. A single answer is generated with expensive algorithms (e.g., $\sqrt{2}\approx1.41421...$) ...
- 141
2
votes
Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs
This paper describes a new form of incremental computation: taking derivatives on data-type-valued functions (e.g. List-valued functions).
http://www.informatik.uni-marburg.de/~pgiarrusso/papers/...
- 773
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 ...
- 36.7k
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 ...
- 121
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) ...
- 839
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
...
- 548
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 $\...
- 18.1k
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 ...
- 1,046
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 ...
- 5,446
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 ...
- 11
Only top scored, non community-wiki answers of a minimum length are eligible