A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number

DOI10.1007/S10801-018-0851-1zbMATH Open1494.68147OpenAlexW2898531758WikidataQ129047924 ScholiaQ129047924MaRDI QIDQ2011387FDOQ2011387

Authors Emanuele Rodaro

Publication date 6 December 2019

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

packing numberWedderburn-Artin theoremsynchronizing automatonsimple automatonsemisimple automatonČerný's conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We show that if a semisimple synchronizing automaton with $n$ states has a minimal reachable non-unary subset of cardinality $rge2$, then there is a reset word of length at most $(n-1)D(2,r,n)$, where $D(2,r,n)$ is the $2$-packing number for families of $r$-subsets of $[1,n]$.

Recommendations

• scientific article; zbMATH DE number 846959
• Lower bounds for the length of reset words in Eulerian automata
• Computing the shortest reset words of synchronizing automata
• scientific article; zbMATH DE number 7228447
• Lower Bounds for the Length of Reset Words in Eulerian Automata

Cites work

• scientific article; zbMATH DE number 1633834 (Why is no real title available?)
• scientific article; zbMATH DE number 7228447 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1142311 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• scientific article; zbMATH DE number 3328165 (Why is no real title available?)
• A quadratic upper bound on the size of a synchronizing word in one-cluster automata
• Automata with finite congruence lattices
• Matrix Mortality and the Černý-Pin Conjecture
• On two Combinatorial Problems Arising from Automata Theory
• Primitive and irreducible automata
• Primitive digraphs with large exponents and slowly synchronizing automata
• Representation theory of finite semigroups, semigroup radicals and formal language theory
• Reset words for commutative and solvable automata
• Semisimple synchronizing automata and the Wedderburn-Artin theory
• Synchronizing Automata and the Černý Conjecture
• Synchronizing automata preserving a chain of partial orders
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing generalized monotonic automata
• Synchronizing groups and automata
• The Černý conjecture for aperiodic automata
• The Černý conjecture for automata respecting intervals of a directed graph
• The Černý conjecture for one-cluster automata with prime length cycle

Cited in

(2)

• Estimation of the length of reset words for automata with simple idempotents
• scientific article; zbMATH DE number 7228447 (Why is no real title available?)

This page was built for publication: A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number

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