9
Maybe the keyword you are looking for is "Implicit Complexity". It is more general than Curry-Howard correspondence, but several lines of research investigate along the axis you are interested in. You can check for instance the publications of Patrick Baillot for many references and pointers.
For a little self-promotion, here are for instance two ...
2
It is unlikely to have a "name" because it is trivial: it can be solved with a hashtable, array, self-balanced binary search tree, or any other data structure that maps $x$ to $X_i$.
2
After discussing it further with a3nm, I propose an algorithm that is
different than Neal's algorithm and works in a more general
setting. The approach gives polynomial delay algorithm but it uses
exponential space.
The only two properties that we will be using are :
(1) The problem is self-reducible, in the sense that if I am given an
automaton $A$ and $u \...
Only top voted, non community-wiki answers of a minimum length are eligible
