Complexity of problems concerning reset words for cyclic and Eulerian automata

DOI10.1016/J.TCS.2012.04.022zbMATH Open1279.68163OpenAlexW2175473110MaRDI QIDQ442134FDOQ442134

Authors: Pavel Martyugin 

Publication date: 9 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.04.022

Recommendations

• Complexity of problems concerning reset words for cyclic and Eulerian automata
• Complexity of a problem concerning reset words for Eulerian binary automata
• Complexity of a problem concerning reset words for Eulerian binary automata
• Complexity of problems concerning reset words for some partial cases of automata
• The complexity of finding reset words in finite automata

zbMATH Keywords

computational complexitysynchronizationautomatareset words

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Synchronizing finite automata on Eulerian digraphs.
• Reset Sequences for Monotonic Automata
• On two Combinatorial Problems Arising from Automata Theory
• Title not available (Why is that?)
• Synchronizing automata preserving a chain of partial orders
• The complexity of finding reset words in finite automata
• Synchronizing monotonic automata
• Composition sequences for functions over a finite domain.
• Complexity of problems concerning reset words for some partial cases of automata

Cited In (14)

• State complexity of the set of synchronizing words for circular automata and automata over binary alphabets
• Title not available (Why is that?)
• On the height of a finite automaton
• Complexity of a problem concerning reset words for Eulerian binary automata
• The complexity of finding reset words in finite automata
• The relation between preset distinguishing sequences and synchronizing sequences
• Lower Bounds for the Length of Reset Words in Eulerian Automata
• Complexity of problems concerning reset words for some partial cases of automata
• Lower bounds for the length of reset words in Eulerian automata
• Finding short synchronizing words for prefix codes
• An extremal series of Eulerian synchronizing automata
• Complexity of problems concerning reset words for cyclic and Eulerian automata
• Synchronizing series-parallel deterministic finite automata with loops and related problems
• Complexity of a problem concerning reset words for Eulerian binary automata

This page was built for publication: Complexity of problems concerning reset words for cyclic and Eulerian automata

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