Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata
From MaRDI portal
Publication:5250279
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
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
