minicomplexity
relational path
 Given two binary relations 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 relations.
 For every $h\geq1$, relational path$h$ (or just rpath$h$) is defined over the alphabet $\bigl( [h]\cup\mathbb{P}([h]{\times}[h]) \bigr)\times\{\mathtt{l},\mathtt{r}\}$ of all pairs consisting of a number from $[h]=\{0,1,\dots,h{-}1\}$ or a binary relation on $[h]$ and of a side tag. Every instance of rpath$h$ is of the form $(x,\mathtt{l})(A,\mathtt{l})(B,\mathtt{r})(y,\mathtt{r})\,$, for some $x,y\in[h]$ and $A,B\subseteq[h]{\times}[h]$. 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 relation. E.g., if $h=5$ and \begin{aligned} A&=\{(0,3),(1,1),(1,3),(2,0),(2,2),(2,4),(4,4)\} \\ B&=\{(0,0),(1,3),(1,4),(4,1),(4,3)\} \,, \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 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=3$, then the graph is the interpretation of the resulting instance of rpath$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 2006, as a problem in 2N\1N which witnesses the exact value of the trade-off in the conversion from 2NFAs to 1NFAs and from 2NFAs to 1DFAs. The name “relational path” is suggested by this site. huh? See relational match and relational zero-match for two variants where we ask for cycles. See functional path for the restriction to functions.
 – no record –
 – no record –