minicomplexity
relational zero-match
 Given two binary relations on $[h]$, check that it is possible to start from $0$ and return to it after an even number of alternate applications of the relations.
 For every $h\geq1$, relational zero-match$h$ (or just rzmatch$h$) is defined over the alphabet $\mathbb{P}([h]{\times}[h])\times\{\mathtt{l},\mathtt{r}\}$ of all pairs consisting of a binary relation on $[h]=\{0,1,\dots,h{-}1\}$ and of a side tag. Every instance of rzmatch$h$ is of the form $(A,\mathtt{l})(B,\mathtt{r})\,$, for some $A,B\subseteq[h]{\times}[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 relation. E.g., if $h=5$ and \begin{aligned} A&=\{(0,2),(1,1),(1,3),(2,3),(2,4),(4,4)\} \\ B&=\{(0,1),(1,0),(1,3),(1,4),(2,2),(4,1)\} \,, \end{aligned} then the symbols $(A,\mathtt{l})$ and $(B,\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 rzmatch$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 2N\1D which witnesses the asymptotic value of the trade-off in the conversion from 2NFAs to 1DFAs. (Actually defined over a $4$-symbol alphabet.) The name “relational zero-match” was suggested by Kapoutsis Pighizzini 2011. See relational match for the variant where we ask for any cycle, and relational path for a variant where we ask for a path. See functional zero-match for the restriction to functions.
 – no record –
 – no record –