Pin conjecture for matching automata
Zihao Wang, Qingxia Long, Yong Dong He · International Journal of Embedded Systems · 2024
Let A = (S, A, δ) be an n-state automaton over m input letters.The merging graph of A is the simple undirected graph G = (S, E) of which the edge set E consists of all binary mergable sets of A .The automaton A is said to be matching if E is a matching of the state set S. The matchingness of A can be decided in O(nm) times.If A is a matching automaton, then the rank of A is n/2 and, for any integer r with n/2 ≤ r ≤ n, an r-rank input word of A having length at most ∑ n-r i=0 i can be computed in O(n 2 + nm) times.This illustrates that Pin conjecture (and hence rank conjecture) is true for matching automata.Furthermore, it is shown that the tight bound for the lengths of the shortest r-rank input words of n-state matching automata is ∑ n-r i=0 i.