Pin conjecture for matching automata

Zihao Wang, Qingxia Long, Yong HeInternational Journal of Embedded Systems 2024 · DOI

TL;DR

This paper introduces a new class of computational models called matching automata and proves that the long-standing Pin conjecture (a generalization of the famous Černý conjecture) holds true for them. The authors provide an efficient $O(nm)$ algorithm to identify these automata and establish a tight mathematical bound for the length of words needed to reduce the system's state to a specific "rank."

What Problem Does This Paper Address?

In control theory and robotics, a classic problem is: "How do you regain control of a device if you don't know its current state?" This is modeled using synchronizing automata—systems where a specific sequence of inputs (a "synchronizing word") resets the machine to a single known state, regardless of where it started.

The Černý conjecture (1964) suggests that for any $n$-state synchronizing automaton, the shortest reset word is at most $(n-1)^2$. The Pin conjecture (1978) is an even more ambitious generalization: it posits that if an automaton can be compressed to $r$ states (an "$r$-rank" word), the shortest such word has a length no greater than $(n-r)^2$.

While the Pin conjecture was actually proven false in the general case by Jarkko Kari in 2001, researchers still seek to identify specific classes of automata where it does hold. This paper identifies "matching automata" as one such class.

Methods

The authors define a matching automaton based on its "merging graph." In this graph, an edge exists between two states if there is an input sequence that transitions both states into the same single state. An automaton is "matching" if this graph is 1-regular—meaning every state is paired with exactly one other state that it can merge with.

The paper contributes two primary algorithmic tools:

  1. Algorithm 1: A method to determine if a given $n$-state automaton with $m$ input letters is a matching automaton in $O(nm)$ time.
  2. Algorithm 2: An extension of Pin’s 1983 work that computes an $r$-rank input word for these automata in $O(nm + n^2)$ time.

The theoretical core of the paper uses induction and the properties of "defective letters" (inputs that cause at least one pair of states to merge) to prove that the rank of the automaton behaves predictably under specific input sequences.

Datasets

As a theoretical study in automata theory and combinatorics, this paper does not use empirical datasets or machine learning benchmarks. Instead, it utilizes a constructed mathematical model called the extreme matching automaton ($M_n$). This specific automaton serves as a "worst-case scenario" to prove that the bounds derived by the authors are "tight" (meaning they cannot be improved further).

Key Insights and Ideas

  • The "Aha" Moment: The authors realized that if the merging possibilities of an automaton are restricted to a perfect matching (a set of disjoint pairs), the complexity of state reduction drops significantly. This structure prevents the "chaotic" merging patterns that usually make the Pin conjecture fail.
  • Stronger than Pin: Interestingly, for matching automata, the authors found a bound that is actually much smaller than Pin's $(n-r)^2$. They proved the length is at most $\sum_{i=0}^{n-r} i$, which simplifies to $\frac{(n-r)^2 + (n-r)}{2}$.
  • Rank Predictability: In matching automata, the rank (the number of reachable states after an input) decreases in a very linear, controlled fashion, which allows for the calculation of exact shortest-path lengths.

Key Results

  • Validation of Conjectures: The paper formally proves that both the Pin conjecture and the related Rank conjecture are true for all matching automata.
  • Tight Bounds: The shortest $r$-rank word for an $n$-state matching automaton is exactly $\sum_{i=0}^{n-r} i$. For example, to reduce a 10-state matching automaton to rank 5, you would need a word of length $0+1+2+3+4+5 = 15$.
  • Efficiency: The authors demonstrate that we can not only prove these bounds exist but also find the words themselves using computationally efficient algorithms ($O(nm + n^2)$).

Limitations and Future Work

The primary limitation is that "matching automata" represent a very specific subset of all possible automata. While the Pin conjecture holds here, the search continues for other, broader classes of automata that satisfy these bounds.

The authors suggest that their algorithmic approach—labeling members of merging families to avoid "troublesome comparisons"—could potentially be adapted to study other classes of synchronizing automata. Future research may look into "near-matching" graphs or other regular graph structures to see if the Pin conjecture's validity extends further into the landscape of discrete control systems.

Summary updated

Abstract

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.
BibTeX
@article{wang2024pin,
  author = {Zihao Wang and Qingxia Long and Yong He},
  title = {{Pin conjecture for matching automata}},
  journal = {International Journal of Embedded Systems},
  year = {2024},
  doi = {10.1504/ijes.2024.144370},
}
Figure