Open Problems in Automata Theory
Contributions from the Autobóz Community
Menu
Close
Home
Archives
Tags
autóboz website
There are 52 posts in total till now.
2024
Apr 29, 2024
23.6 Target for pushdown RBN
Apr 22, 2024
23.3 Reachability problem for thin 1-GVASS
Apr 22, 2024
23.4 Bounds on the length of a coverability path in VASS
2023
Sep 16, 2023
23.1 TARGET in asynchronous shared-memory systems
Aug 09, 2023
23.5 Linear loop synthesis: When d variables are not enough.
Jul 25, 2023
23.2 $o(n^2)$-time algorithm for coverability in 1-VASS
2022
Sep 16, 2022
22.1 Complexity of fixed VAS reachability
Sep 16, 2022
22.2 Paired Counter Automata
Sep 16, 2022
22.3 Universal coverability for Orthant VAS
Sep 16, 2022
22.4 Reconfigurable broadcast networks (RBN)
Sep 16, 2022
22.5 Decidability of $(\min,+)$-weighted automata determinization
Sep 16, 2022
22.6 Completing Partial DFAs to Synchronizing DFAs
Sep 16, 2022
22.7 Equivalent k-HD-TA for a given 1-NTA
Sep 16, 2022
22.12 3-decomposition Conjecture
Sep 16, 2022
22.13 Büchi automata using graph neural networks
Sep 16, 2022
22.14 Transformation monoid minimisation
Sep 16, 2022
22.15 Universal Positivity Set
Sep 16, 2022
22.16 Is Markov reachability problem Skolem-Hard for Ergodic Markov chains?
Sep 16, 2022
22.17 Eventual non-negativity of Matrices
Sep 16, 2022
22.18 Learning sequences
Sep 16, 2022
22.19 Membership in Reversed Partially-Ordered Automata
Sep 16, 2022
22.10 The Parity Language
Sep 16, 2022
22.9 Constructive Zermelo's Problem
Sep 16, 2022
22.8 From two-way to one-way transducers, revisited
2020
Nov 03, 2020
20.10 Tighten the complexity of solving random-turn games
Nov 03, 2020
20.11 The sequential flow problem
Nov 03, 2020
20.12 Succinctness of GFG pushdown automata
Nov 03, 2020
20.9 Memory requirements for generalized reachability games
Aug 03, 2020
20.8 Good games for good-for-games automata
Jul 21, 2020
20.1 Universality of letter-bounded CFLs
Jul 21, 2020
20.2 Deterministic separability of nondeterministic timed languages
Jul 21, 2020
20.3 Prime DOCAs
Jul 21, 2020
20.4 Populations of Markov decision processes, what we know and an open question
Jul 21, 2020
20.5 Regular antichain subset of the iteration of a regular language
Jul 21, 2020
20.6 Branching Immediate Observation nets
Jul 21, 2020
20.7 Equivalence of Cost Register Automata: the quest for decidability
2019
Jul 18, 2019
19.17 Existence of a universal amplifier of selection
Jul 18, 2019
19.16 Weak validation of tree-languages by extended automata
Jul 18, 2019
19.15 The busy beaver problem for population protocols
Jul 18, 2019
19.14 Continuous reachability in ordered data VAS
Jul 18, 2019
19.13 Does a $(\textsf{min,+})$-WA preserve REG by inverse image?
Jul 18, 2019
19.12 Reachability for bounded branching VASS
Jul 18, 2019
19.11 Shortest runs in 3-D VASS
Jul 18, 2019
19.10 Variants of one-counter systems universality
Jul 18, 2019
19.8 Logic and automata for multiply nested-words
Jul 18, 2019
19.7 Membership in logical classes for (succinct) finite automata
Jul 18, 2019
19.6 HyperLTL satisfiability
Jul 18, 2019
19.5 On unambiguous grammars
Jul 18, 2019
19.4 Separating words problem
Jul 18, 2019
19.3 Universality for unambiguous automata
Jul 18, 2019
19.2 SafeLTL
Jul 18, 2019
19.1 Deciding upperboundedness of \(\bbZ\)-CCRA