Reset sink complexity of regular ideals

MaRDI QIDQ6894347zbMATH OpenFDO

Authors Achille Frigeri, Emanuele Rodaro

Publication date 25 November 2025

Published in Journal of Automata, Languages and Combinatorics (Search for Journal in Brave)

Full work available at URL https://jalc.de/issues/2025/issue_30_1-3/jalc-2025-077-094.php

zbMATH Keywords

automata with sinkdecompositions of idealssynchronizing automataČerný conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number
• A quadratic upper bound on the size of a synchronizing word in one-cluster automata
• Algebraic synchronization criterion and computing reset words
• An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
• An extremal problem for two families of sets
• An improvement to a recent upper bound for synchronizing words of finite automata
• Finitely generated ideal languages and synchronizing automata
• scientific article; zbMATH DE number 7228447 (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?)
• Ideal regular languages and strongly connected synchronizing automata
• Missing factors of ideals and synchronizing automata
• On two Combinatorial Problems Arising from Automata Theory
• Principal ideal languages and synchronizing automata
• Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete
• Regular ideal languages and synchronizing automata
• Representations of regular ideals in finite automata
• Reset complexity of ideal languages over a binary alphabet
• Reset Sequences for Monotonic Automata
• Semisimple synchronizing automata and the Wedderburn-Artin theory
• Strongly connected synchronizing automata and the language of minimal reset words
• Synchronization of finite automata
• Synchronizing Automata and the Černý Conjecture
• Synchronizing automata preserving a chain of partial orders
• Synchronizing automata with finitely many minimal synchronizing words
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing generalized monotonic 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
• Trim Strongly Connected Synchronizing Automata and Ideal Languages
• Černý's conjecture and the road colouring problem

This page was built for publication: Reset sink complexity of regular ideals

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