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.68147arXiv1711.00651OpenAlexW2898531758WikidataQ129047924 ScholiaQ129047924MaRDI QIDQ2011387FDOQ2011387

Authors: Emanuele Rodaro 

Publication date: 6 December 2019

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

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]$.

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

Recommendations

• Publication:4864787
• Lower bounds for the length of reset words in Eulerian automata
• Computing the shortest reset words of synchronizing automata
• scientific article
• Lower Bounds for the Length of Reset Words in Eulerian Automata

zbMATH Keywords

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Synchronizing Automata and the Černý Conjecture
• Title not available (Why is that?)
• Synchronizing generalized monotonic automata
• Title not available (Why is that?)
• Synchronizing finite automata on Eulerian digraphs.
• A quadratic upper bound on the size of a synchronizing word in one-cluster automata
• Representation theory of finite semigroups, semigroup radicals and formal language theory
• On two Combinatorial Problems Arising from Automata Theory
• The Černý conjecture for aperiodic automata
• Title not available (Why is that?)
• The Černý conjecture for one-cluster automata with prime length cycle
• Synchronizing automata preserving a chain of partial orders
• Primitive digraphs with large exponents and slowly synchronizing automata
• Synchronizing groups and automata
• Automata with finite congruence lattices
• Title not available (Why is that?)
• The Černý conjecture for automata respecting intervals of a directed graph
• Reset words for commutative and solvable automata
• Matrix Mortality and the Černý-Pin Conjecture
• Primitive and irreducible automata
• Algebraic synchronization criterion and computing reset words
• Semisimple synchronizing automata and the Wedderburn-Artin theory
• Title not available (Why is that?)

Cited In (2)

• Estimation of the length of reset words for automata with simple idempotents
• Title not available (Why is that?)

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)