Synchronization problems in automata without non-trivial cycles

DOI10.1016/j.tcs.2018.12.026zbMath1429.68133arXiv1702.08144OpenAlexW4229511693MaRDI QIDQ5919579

Andrew Ryzhikov

Publication date: 20 August 2019

Published in: Theoretical Computer Science, Implementation and Application of Automata (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityinapproximabilitysynchronizing automatasynchronizing automatonweakly acyclic automatasubset ranksynchronizable setweakly acyclic automaton

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

Constrained synchronization and subset synchronization problems for weakly acyclic automata, Learning from positive and negative examples: dichotomies and parameterized algorithms, State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs, Unnamed Item, Constrained synchronization and commutativity, Synchronization problems in automata without non-trivial cycles, Synchronizing series-parallel deterministic finite automata with loops and related problems, State complexity of permutation and related decision problems on alphabetical pattern constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Synchronizing monotonic automata
• A survey of known results and research areas for \(n\)-queens
• Languages of R-trivial monoids
• Reset words for commutative and solvable automata
• Synchronizing finite automata on Eulerian digraphs.
• Rank of a finite automaton
• Polynomial complete problems in automata theory
• Model-based testing of reactive systems. Advanced lectures.
• Completely Reachable Automata
• Subset Synchronization and Careful Synchronization of Binary Finite Automata
• On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs
• On Two Algorithmic Problems about Synchronizing Automata
• Strong Inapproximability of the Shortest Reset Word
• Primitive Sets of Nonnegative Matrices and Synchronizing Automata
• Reset Sequences for Monotonic Automata
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Synchronizing Automata and the Černý Conjecture
• Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA
• On two Combinatorial Problems Arising from Automata Theory
• On the Road Coloring Problem
• Subset Synchronization in Monotonic Automata
• Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata
• Sur le coloriage des graphs
• Synchronization problems in automata without non-trivial cycles