Title: Pin conjecture for matching automata

Authors: Zihao Wang; Qingxia Long; Yong He

Addresses: School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan, Hunan, China ' School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan, Hunan, China ' School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan, Hunan, China

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 A 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² + 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.

Keywords: r-rank input word; Pin conjecture; merging graph; matching automaton; extreme matching automaton.

DOI: 10.1504/IJES.2024.144370

International Journal of Embedded Systems, 2024 Vol.17 No.3/4, pp.224 - 236

Received: 27 Oct 2023
Accepted: 18 Mar 2024
Published online: 10 Feb 2025 *