Semicomputable points in Euclidean spaces
From MaRDI portal
Publication:5092426
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
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
