Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata

DOI10.1142/S0129054115500057zbMath1312.68125OpenAlexW2048946385MaRDI QIDQ5250279

Uraz Cengiz Türker, Hüsnü Yenigün

Publication date: 19 May 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054115500057

zbMATH Keywords

reset wordsmonotonic automatasynchronizable automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Synchronization problems in automata without non-trivial cycles ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems

Cites Work

• Synchronizing monotonic automata
• Synchronizing automata preserving a chain of partial orders
• The annulation threshold for partially monotonic automata
• A survey of known results and research areas for \(n\)-queens
• Approximation algorithms for combinatorial problems
• Polynomial complete problems in automata theory
• Using a minimal number of resets when testing from a finite state machine
• Relationships between nondeterministic and deterministic tape complexities
• Algorithmic construction of sets for k -restrictions
• A threshold of ln n for approximating set cover
• On minimizing the lengths of checking sequences
• Reduced length checking sequences
• Reset Sequences for Monotonic Automata
• Testing Software Design Modeled by Finite-State Machines
• On the hardness of approximating minimization problems
• A Method for the Design of Fault Detection Experiments

This page was built for publication: Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata