Semicomputable points in Euclidean spaces

DOI10.4230/LIPIcs.MFCS.2019.63OpenAlexW2950231091MaRDI QIDQ5092426

Henning Fernau, Markus Holzer, Petra Wolf, Stefan Hoffmann, Vladimir V. Gusev, Mikhail V. Volkov

Publication date: 21 July 2022

Full work available at URL: https://hal.inria.fr/hal-02154825

zbMATH Keywords

computational complexitysynchronizationfinite automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (12)

Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ Constrained synchronization for monotonic and solvable automata and automata with simple idempotents ⋮ Synchronization of Parikh automata ⋮ Completely distinguishable automata and the set of synchronizing words ⋮ Binary and circular automata having maximal state complexity for the set of synchronizing words ⋮ Ideal separation and general theorems for constrained synchronization and their application to small constraint automata ⋮ Constrained synchronization and commutativity ⋮ Computational complexity of synchronization under regular commutative constraints ⋮ Sync-maximal permutation groups equal primitive permutation groups ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems

Cites Work

• Primitive digraphs with large exponents and slowly synchronizing automata
• Improved upper bounds on synchronizing nondeterministic automata
• Enumeration and random generation of accessible automata
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• Problems on finite automata and the exponential time hypothesis
• Approximating the minimum length of synchronizing words is hard
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Polynomial complete problems in automata theory
• Preimage problems for deterministic finite automata
• Enumeration and generation with a string automata representation
• Model-based testing of reactive systems. Advanced lectures.
• Synchronizing Automata of Bounded Rank
• A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
• Synchronizing Strategies under Partial Observability
• Polynomial-time algorithm for the orbit problem
• Synchronizing Automata and the Černý Conjecture
• An improvement to a recent upper bound for synchronizing words of finite automata
• Switching and Finite Automata Theory
• Lower Bounds for Synchronizing Word Lengths in Partial Automata
• A Census of Finite Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Semicomputable points in Euclidean spaces