Extremal Binary PFAs with Small Number of States

DOI10.1142/S0129054122440038MaRDI QIDQ6169960zbMATH OpenOpenAlexFDO

Authors Stijn Cambie, Michiel De Bondt, Henk Don

Publication date 15 August 2023

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.13927

zbMATH Keywords

finite automatasynchronizationČerný conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: The largest known reset thresholds for DFAs are equal to $(n-1{)}^2$, where $n$ is the number of states. This is conjectured to be the maximum possible. PFAs (with partial transition function) can have exponentially large reset thresholds. This is still true if we restrict to binary PFAs. However, asymptotics do not give conclusions for fixed $n$. We prove that the maximal reset threshold for binary PFAs is strictly greater than $(n-1{)}^2$ if and only if $ngeq6$. These results are mostly based on the analysis of synchronizing word lengths for a certain family of binary PFAs. This family has the following properties: it contains the well-known v{C}ern'y automata; for $nleq10$ it contains a binary PFA with maximal possible reset threshold; for all $ngeq6$ it contains a PFA with reset threshold larger than the maximum known for DFAs. Analysis of this family reveals remarkable patterns involving the Fibonacci numbers and related sequences such as the Padovan sequence. We derive explicit formulas for the reset thresholds in terms of these recurrent sequences. Asymptotically the v{C}ern'y family gives reset thresholds of polynomial order. We prove that PFAs in the family are not extremal for $ngeq41$. For that purpose, we present an improvement of Martyugin's prime number construction of binary PFAs.

Cites work

• An extremal problem for two families of sets
• An improvement to a recent upper bound for synchronizing words of finite automata
• Extremal binary PFAs in a Černý family
• scientific article; zbMATH DE number 7152073 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• Lower bounds for synchronizing word lengths in partial automata
• Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata
• On two Combinatorial Problems Arising from Automata Theory
• Subset synchronization and careful synchronization of binary finite automata
• Synchronizing Automata and the Černý Conjecture

Cited in

(1)

• Extremal binary PFAs in a Černý family

This page was built for publication: Extremal Binary PFAs with Small Number of States

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169960)