An extremal series of Eulerian synchronizing automata

DOI10.1007/978-3-662-53132-7_31zbMATH Open1362.68156arXiv1604.02879OpenAlexW3102686480MaRDI QIDQ2817403FDOQ2817403

Authors: Marek Szykuła, Vojtěch Vorel 

Publication date: 30 August 2016

Published in: Developments in Language Theory (Search for Journal in Brave)

Abstract: We present an infinite series of $n$-state Eulerian automata whose reset words have length at least $(n^2-3)/2$. This improves the current lower bound on the length of shortest reset words in Eulerian automata. We conjecture that $(n^2-3)/2$ also forms an upper bound for this class and we experimentally verify it for small automata by an exhaustive computation.

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

Recommendations

• Lower bounds for the length of reset words in Eulerian automata
• Complexity of problems concerning reset words for cyclic and Eulerian automata
• Lower Bounds for the Length of Reset Words in Eulerian Automata
• Synchronizing automata on quasi-Eulerian digraph
• Synchronizing Automata with Extremal Properties

zbMATH Keywords

reset wordsynchronizing automatonEulerian automatonreset threshold

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Synchronizing Automata and the Černý Conjecture
• Synchronizing generalized monotonic automata
• Synchronizing finite automata on Eulerian digraphs.
• A quadratic upper bound on the size of a synchronizing word in one-cluster automata
• Reset Sequences for Monotonic Automata
• On two Combinatorial Problems Arising from Automata Theory
• The Černý conjecture for aperiodic automata
• The Černý conjecture for one-cluster automata with prime length cycle
• Synchronizing automata preserving a chain of partial orders
• Slowly synchronizing automata and digraphs
• Primitive digraphs with large exponents and slowly synchronizing automata
• The averaging trick and the Černý conjecture
• The Černý conjecture for automata respecting intervals of a directed graph
• Strongly transitive automata and the Černý conjecture
• Generating small automata and the Černý conjecture
• Estimation of the length of reset words for automata with simple idempotents
• Shortest synchronizing strings for Huffman codes
• Computing the shortest reset words of synchronizing automata
• Synchronizing Automata with Extremal Properties
• Lower bounds for the length of reset words in Eulerian automata
• Experiments with Synchronizing Automata
• Synchronizing quasi-Eulerian and quasi-one-cluster automata

Cited In (8)

• Attainable values of reset thresholds
• On randomized generation of slowly synchronizing automata
• Synchronizing Automata with Extremal Properties
• Černý's conjecture and the road colouring problem
• Lower bounds for the length of reset words in Eulerian automata
• Title not available (Why is that?)
• Synchronizing quasi-Eulerian and quasi-one-cluster automata
• Synchronizing automata on quasi-Eulerian digraph

This page was built for publication: An extremal series of Eulerian synchronizing automata

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