2014/11/28 by Pavel Panteleev, Panteleev, Pavel · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #20D60 (Secondary) #68Q45 (Primary) #68Q70 #Chemical Synthesis and Analysis #DNA and Biological Computing #F.1.1 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Mathematical Dynamics and Fractals #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1412.0034
openalex publication_date 2014/11/28 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
We investigate the length \ℓ(n,k) of a shortest preset distinguishing\nsequence (PDS) in the worst case for a k-element subset of an n-state Mealy\nautomaton. It was mentioned by Sokolovskii that this problem is closely related\nto the problem of finding the maximal subsemigroup diameter\n\ℓ(\Tn) for the full transformation semigroup \Tn of an\nn-element set. We prove that\n\ℓ(\Tn)=2n\exp \√(\(n)/(2)\ln n)(1+ o(1)) as\nn\→\∞ and, using approach of Sokolovskii, find the asymptotics of\n\log2 \ℓ(n,k) as n,k\→\∞ and k/n\→ a\∈ (0,1).\n