minicomplexity
functional zero-match
 Given two partial functions on $[h]$, check that it is possible to start from $0$ and return to it after an even number of alternate applications of the functions.
 For every $h\geq1$, functional zero-match$h$ (or just fzmatch$h$) is defined over the alphabet $([h]{\rightharpoonup}[h])\times\{\mathtt{l},\mathtt{r}\}$ of all pairs consisting of a partial function on $[h]=\{0,1,\dots,h{-}1\}$ and of a side tag. Every instance of fzmatch$h$ is of the form $(\alpha,\mathtt{l})(\beta,\mathtt{r})\,$, for some $\alpha,\beta:[h]{\rightharpoonup}[h]$. Each symbol 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,2),(1,1),(2,3),(4,4)\} \\ \beta &=\{(0,0),(1,4),(2,1),(4,0)\} \,, \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 overlaying the two graphs of the individual symbols. E.g., for the symbols above, the interpretation is: If this graph contains a cycle through the top vertex of the left column, we say it is a zero-match. An instance is positive if its graph is a zero-match. E.g., the above instance of fzmatch$5$ is positive, because of the bold cycle. In contrast, an instance whose symbols represent the next two graphs on the left is negative, because none of the cycles contained in their overlay on the right pass through the top left vertex.
 Introduced by Berman Lingas 1977, as a problem in 2D\1D which witnesses the asymptotic value of the trade-off in the conversion from 2DFAs to 1DFAs. (Actually defined over a $4$-symbol alphabet.) The name “functional zero-match” was suggested by Kapoutsis Pighizzini 2011. See functional match for the variant where we ask for any cycle, and functional path for a variant where we ask for a path. See relational zero-match for the generalization to relations.
 – no record –
 – no record –