minicomplexity
functional path
 Given two partial functions on $[h]$ and two points in $[h]$, check that it is possible to connect the points by an even number of alternate applications of the functions.
 For every $h\geq1$, functional path$h$ (or just fpath$h$) is defined over the alphabet $\bigl( [h]\cup([h]{\rightharpoonup}[h]) \bigr)\times\{\mathtt{l},\mathtt{r}\}$ of all pairs consisting of a number from $[h]=\{0,1,\dots,h{-}1\}$ or a partial function on $[h]$ and of a side tag. Every instance of fpath$h$ is of the form $(x,\mathtt{l})(\alpha,\mathtt{l})(\beta,\mathtt{r})(y,\mathtt{r})\,$, for some $x,y\in[h]$ and $\alpha,\beta:[h]{\rightharpoonup}[h]$ such that $\beta(y)$ is undefined. Each of the two inner symbols of an instance is interpreted as an $h$-tall $2$-column directed graph, in which the direction of the arrows is selected by the tag ($\mathtt{l}$: left-to-right; $\mathtt{r}$: right-to-left) and the end-points of the arrows are selected by the function. E.g., if $h=5$ and \begin{aligned} \alpha&=\{(0,1),(1,2),(2,0),(4,4)\} \\ \beta &=\{(0,0),(1,4),(2,3),(3,1)\} \,, \end{aligned} then the symbols $(\alpha,\mathtt{l})$ and $(\beta,\mathtt{r})$ above represent respectively the graphs: The full instance is interpreted as the graph that we get by first overlaying the graphs of the two inner symbols, and then using the two outer symbols to designate an entry on the left column and an exit on the right column. E.g., if we continue the previous example with $x=2$ and $y=4$, then the graph is the interpretation of the resulting instance of fpath$5$. An instance is positive if its graph contains a path from entry to exit. E.g., the instance drawn above is positive, because of the bold path. In contrast, an instance whose first and second half represent the next two graphs on the left is negative, because their overlay on the right contains no entry-to-exit path.
 Introduced by Kapoutsis 2005, as a problem in 2D\1N which witnesses the exact value of the trade-off in the conversion from 2DFAs to 1NFAs and from 2DFAsto 1DFAs. The name “functional path” is suggested by this site. huh? See functional match and functional zero-match for two variants where we ask for cycles. See relational path for the generalization to relations.
 – no record –
 – no record –