Open Problems in Automata Theory

Contributions from the Autobóz Community
Menu Close
  • Home
  • Archives
  • Categories
  • Tags
  • About
  • autóboz website
VASS pvass parity games channels markov decision processes parameterized games Kleene algebra linear dynamical systems reachability trees game distributed networks parameterized verification weighted automata peacewise-testable languages Nash equilibria context-free grammars Petri nets neural networks Markov chains subtyping bi-reachablility XML descriptional complexity temporal logic graphs counter machines networks infinite words circuits vass communicating automata positionality population protocols valence systems automata invariants transducers coverability continuity logic Petri nets with data petri nets complexity separation first-order logic CFL cost register automata pushdown automata fixpoint session types stochastic processes two variables verification algebra languages timed automata Games on graphs pushdown Skolem problem string constraints games emptiness checking

algebra

Jul 14, 2024

24.19 Reachability in Reversible Data VASS

Aug 09, 2023

23.5 Linear loop synthesis: When d variables are not enough.

Sep 16, 2022

22.14 Transformation monoid minimisation

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

automata

Jul 14, 2024

24.19 Reachability in Reversible Data VASS

Jul 12, 2024

24.16 Speed of victory in adversarial population games

Jul 05, 2024

24.7 Minimality for Deterministic Suffix-reading Automata

Jul 05, 2024

24.9 Is the Hierarchy of Valence Systems with Open Reachability Proper?

Jul 05, 2024

24.12 Fine-grained complexity of reachability in one-counter automata

Sep 16, 2023

23.1 TARGET in asynchronous shared-memory systems

Sep 16, 2022

22.2 Paired Counter Automata

Sep 16, 2022

22.6 Completing Partial DFAs to Synchronizing DFAs

Sep 16, 2022

22.13 Büchi automata using graph neural networks

Sep 16, 2022

22.14 Transformation monoid minimisation

Sep 16, 2022

22.19 Membership in Reversed Partially-Ordered 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.5 Regular antichain subset of the iteration of a regular language

Jul 19, 2019

19.16 Weak validation of tree-languages by extended automata

Jul 19, 2019

19.8 Logic and automata for multiply nested-words

Jul 19, 2019

19.7 Membership in logical classes for (succinct) finite automata

Jul 19, 2019

19.4 Separating words problem

Jul 19, 2019

19.3 Universality for unambiguous automata

bi-reachablility

Jul 02, 2024

24.3 Bi-reachability in Petri nets with ordered data

CFL

Nov 03, 2020

20.12 Succinctness of GFG pushdown automata

channels

Jul 05, 2024

24.14 Extending asynchronous subtyping for binary session types

circuits

Sep 16, 2022

22.10 The Parity Language

communicating automata

Jul 05, 2024

24.14 Extending asynchronous subtyping for binary session types

complexity

Jul 05, 2024

24.12 Fine-grained complexity of reachability in one-counter automata

Nov 03, 2020

20.10 Tighten the complexity of solving random-turn games

Nov 03, 2020

20.11 The sequential flow problem

Jul 21, 2020

20.1 Universality of letter-bounded CFLs

Jul 19, 2019

19.12 Reachability for bounded branching VASS

Jul 19, 2019

19.5 On unambiguous grammars

Jul 19, 2019

19.3 Universality for unambiguous automata

context-free grammars

Jul 21, 2020

20.1 Universality of letter-bounded CFLs

Jul 19, 2019

19.5 On unambiguous grammars

continuity

Jul 04, 2024

24.5 Properties of the value function in weighted timed games

Jul 19, 2019

19.13 Does a $(\textsf{min,+})$-WA preserve REG by inverse image?

cost register automata

Jul 21, 2020

20.7 Equivalence of Cost Register Automata: the quest for decidability

Jul 19, 2019

19.1 Deciding upperboundedness of \(\bbZ\)-CCRA

counter machines

Jul 02, 2024

24.4 Language Equivalence between Nondeterministic and Deterministic One-Counter Machines

Sep 16, 2022

22.2 Paired Counter Automata

Jul 21, 2020

20.3 Prime DOCAs

Jul 19, 2019

19.12 Reachability for bounded branching VASS

Jul 19, 2019

19.11 Shortest runs in 3-D VASS

Jul 19, 2019

19.10 Variants of one-counter systems universality

Jul 19, 2019

19.1 Deciding upperboundedness of \(\bbZ\)-CCRA

coverability

Jul 05, 2024

24.8 Coverability in Wait-Only Networks with non-blocking bounded sendings

Jul 25, 2023

23.2 $o(n^2)$-time algorithm for coverability in 1-VASS

descriptional complexity

Jul 19, 2019

19.7 Membership in logical classes for (succinct) finite automata

Jul 19, 2019

19.4 Separating words problem

distributed networks

Jul 05, 2024

24.8 Coverability in Wait-Only Networks with non-blocking bounded sendings

emptiness checking

Jul 05, 2024

24.6 Emptiness-checking for 3-clock Timed Automata with additive constraints

first-order logic

Jul 05, 2024

24.11 Membership of a coverability VASS in FO2

fixpoint

Jul 04, 2024

24.5 Properties of the value function in weighted timed games

game

Jul 04, 2024

24.5 Properties of the value function in weighted timed games

games

Nov 03, 2020

20.9 Memory requirements for generalized reachability games

Nov 03, 2020

20.10 Tighten the complexity of solving random-turn games

Nov 03, 2020

20.12 Succinctness of GFG pushdown automata

Aug 03, 2020

20.8 Good games for good-for-games automata

Jul 21, 2020

20.4 Populations of Markov decision processes, what we know and an open question

Games on graphs

Jul 11, 2024

24.15 Games under delays and loss

graphs

Sep 16, 2022

22.12 3-decomposition Conjecture

infinite words

Nov 03, 2020

20.9 Memory requirements for generalized reachability games

Aug 03, 2020

20.8 Good games for good-for-games automata

Jul 19, 2019

19.2 SafeLTL

invariants

Aug 09, 2023

23.5 Linear loop synthesis: When d variables are not enough.

Kleene algebra

Jun 21, 2024

2024.1 How is $a^* = 1/(1-a)?$

languages

Jul 05, 2024

24.9 Is the Hierarchy of Valence Systems with Open Reachability Proper?

linear dynamical systems

Aug 09, 2023

23.5 Linear loop synthesis: When d variables are not enough.

logic

Sep 16, 2022

22.9 Constructive Zermelo's Problem

Sep 16, 2022

22.10 The Parity Language

Jul 19, 2019

19.8 Logic and automata for multiply nested-words

Jul 19, 2019

19.7 Membership in logical classes for (succinct) finite automata

Jul 19, 2019

19.6 HyperLTL satisfiability

Jul 19, 2019

19.2 SafeLTL

Markov chains

Sep 16, 2022

22.16 Is Markov reachability problem Skolem-Hard for Ergodic Markov chains?

markov decision processes

Jul 21, 2020

20.4 Populations of Markov decision processes, what we know and an open question

Nash equilibria

Jun 27, 2024

24.2 Positional Nash Equilibria

networks

Sep 16, 2022

22.4 Reconfigurable broadcast networks (RBN)

neural networks

Sep 16, 2022

22.13 Büchi automata using graph neural networks

parameterized games

Jul 12, 2024

24.16 Speed of victory in adversarial population games

parameterized verification

Apr 29, 2024

23.6 Target for pushdown RBN

Sep 16, 2023

23.1 TARGET in asynchronous shared-memory systems

parity games

Jun 27, 2024

24.2 Positional Nash Equilibria

peacewise-testable languages

Jul 05, 2024

24.11 Membership of a coverability VASS in FO2

petri nets

Jul 21, 2020

20.6 Branching Immediate Observation nets

Petri nets

Jul 02, 2024

24.3 Bi-reachability in Petri nets with ordered data

Petri nets with data

Jul 02, 2024

24.3 Bi-reachability in Petri nets with ordered data

population protocols

Nov 03, 2020

20.11 The sequential flow problem

Jul 19, 2019

19.15 The busy beaver problem for population protocols

positionality

Jun 27, 2024

24.2 Positional Nash Equilibria

pushdown

Jul 05, 2024

24.9 Is the Hierarchy of Valence Systems with Open Reachability Proper?

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

pushdown automata

Nov 03, 2020

20.12 Succinctness of GFG pushdown automata

Jul 21, 2020

20.1 Universality of letter-bounded CFLs

Jul 21, 2020

20.3 Prime DOCAs

Jul 19, 2019

19.10 Variants of one-counter systems universality

Jul 19, 2019

19.8 Logic and automata for multiply nested-words

Jul 19, 2019

19.5 On unambiguous grammars

pvass

Jul 05, 2024

24.9 Is the Hierarchy of Valence Systems with Open Reachability Proper?

reachability

Jul 05, 2024

24.12 Fine-grained complexity of reachability in one-counter automata

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

Sep 16, 2022

22.3 Universal coverability for Orthant VAS

Jul 19, 2019

19.14 Continuous reachability in ordered data VAS

Jul 19, 2019

19.12 Reachability for bounded branching VASS

Jul 19, 2019

19.11 Shortest runs in 3-D VASS

separation

Jul 21, 2020

20.2 Deterministic separability of nondeterministic timed languages

Jul 19, 2019

19.4 Separating words problem

session types

Jul 05, 2024

24.14 Extending asynchronous subtyping for binary session types

Skolem problem

Sep 16, 2022

22.15 Universal Positivity Set

Sep 16, 2022

22.16 Is Markov reachability problem Skolem-Hard for Ergodic Markov chains?

stochastic processes

Jul 19, 2019

19.17 Existence of a universal amplifier of selection

string constraints

Jul 05, 2024

24.13 Satisfiability of String Constraints with Subsequence relation

subtyping

Jul 05, 2024

24.14 Extending asynchronous subtyping for binary session types

temporal logic

Jul 19, 2019

19.6 HyperLTL satisfiability

Jul 19, 2019

19.2 SafeLTL

timed automata

Jul 05, 2024

24.6 Emptiness-checking for 3-clock Timed Automata with additive constraints

Jul 04, 2024

24.5 Properties of the value function in weighted timed games

Sep 16, 2022

22.7 Equivalent k-HD-TA for a given 1-NTA

Jul 21, 2020

20.2 Deterministic separability of nondeterministic timed languages

transducers

Jul 13, 2024

24.17 Monotone regular functions

Sep 16, 2022

22.8 From two-way to one-way transducers, revisited

trees

Jul 19, 2019

19.16 Weak validation of tree-languages by extended automata

two variables

Jul 05, 2024

24.11 Membership of a coverability VASS in FO2

valence systems

Jul 05, 2024

24.9 Is the Hierarchy of Valence Systems with Open Reachability Proper?

VASS

Jul 14, 2024

24.19 Reachability in Reversible Data VASS

Jul 05, 2024

24.11 Membership of a coverability VASS in FO2

Sep 16, 2022

22.1 Complexity of fixed VAS reachability

Sep 16, 2022

22.3 Universal coverability for Orthant VAS

Jul 19, 2019

19.14 Continuous reachability in ordered data VAS

Jul 19, 2019

19.12 Reachability for bounded branching VASS

Jul 19, 2019

19.11 Shortest runs in 3-D VASS

Jul 19, 2019

19.10 Variants of one-counter systems universality

vass

Jul 05, 2024

24.9 Is the Hierarchy of Valence Systems with Open Reachability Proper?

Jul 05, 2024

24.10 Functions Weakly-Computable by Vector Addition Systems

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

Jul 25, 2023

23.2 $o(n^2)$-time algorithm for coverability in 1-VASS

verification

Jul 05, 2024

24.7 Minimality for Deterministic Suffix-reading Automata

Sep 16, 2023

23.1 TARGET in asynchronous shared-memory systems

weighted automata

Jul 13, 2024

24.18 Lower bounds for determinizability of weighted automata over \(\mathbb Q\)

Sep 16, 2022

22.5 Decidability of $(\min,+)$-weighted automata determinization

Jul 19, 2019

19.13 Does a $(\textsf{min,+})$-WA preserve REG by inverse image?

Jul 19, 2019

19.1 Deciding upperboundedness of \(\bbZ\)-CCRA

XML

Jul 19, 2019

19.16 Weak validation of tree-languages by extended automata

Connect With Us

  • Recent Posts
  • 24.19 Reachability in Reversible Data VASS
    July 14, 2024
  • 24.17 Monotone regular functions
    July 13, 2024
  • 24.18 Lower bounds for determinizability of weighted automata over \(\mathbb Q\)
    July 13, 2024
  • 24.16 Speed of victory in adversarial population games
    July 12, 2024
  • 24.15 Games under delays and loss
    July 11, 2024
  • 24.6 Emptiness-checking for 3-clock Timed Automata with additive constraints
    July 5, 2024

Tags

  • CFL1
  • Games on graphs1
  • Kleene algebra1
  • Markov chains1
  • Nash equilibria1
  • Petri nets1
  • Petri nets with data1
  • Skolem problem2
  • VASS8
  • XML1
  • algebra6
  • automata19
  • bi-reachablility1
  • channels1
  • circuits1
  • communicating automata1
  • complexity7
  • context-free grammars2
  • continuity2
  • cost register automata2
  • counter machines7
  • coverability2
  • descriptional complexity2
  • distributed networks1
  • emptiness checking1
  • first-order logic1
  • fixpoint1
  • game1
  • games5
  • graphs1
  • infinite words3
  • invariants1
  • languages1
  • linear dynamical systems1
  • logic6
  • markov decision processes1
  • networks1
  • neural networks1
  • parameterized games1
  • parameterized verification2
  • parity games1
  • peacewise-testable languages1
  • petri nets1
  • population protocols2
  • positionality1
  • pushdown3
  • pushdown automata6
  • pvass1
  • reachability7
  • separation2
  • session types1
  • stochastic processes1
  • string constraints1
  • subtyping1
  • temporal logic2
  • timed automata4
  • transducers2
  • trees1
  • two variables1
  • valence systems1
  • vass5
  • verification2
  • weighted automata4

Tag Cloud

CFL Games on graphs Kleene algebra Markov chains Nash equilibria Petri nets Petri nets with data Skolem problem VASS XML algebra automata bi-reachablility channels circuits communicating automata complexity context-free grammars continuity cost register automata counter machines coverability descriptional complexity distributed networks emptiness checking first-order logic fixpoint game games graphs infinite words invariants languages linear dynamical systems logic markov decision processes networks neural networks parameterized games parameterized verification parity games peacewise-testable languages petri nets population protocols positionality pushdown pushdown automata pvass reachability separation session types stochastic processes string constraints subtyping temporal logic timed automata transducers trees two variables valence systems vass verification weighted automata

Archives

  • July 202417
  • June 20242
  • April 20243
  • September 20231
  • August 20231
  • July 20231
  • September 202218
  • November 20204
  • August 20201
  • July 20207
  • July 201916
© 2024 Open Problems in Automata Theory All Rights Reserved.
Theme by hipaper