Intractability of decision problems for finite-memory automata
From MaRDI portal
Recommendations
Cites work
Cited in
(30)- An algebraic characterization of deterministic regular languages over infinite alphabets.
- Computational complexity of decision problems on self-verifying finite automata
- Problems on finite automata and the exponential time hypothesis
- Exact complexity of problems of incompletely specified automata
- The containment problem for unambiguous register automata and unambiguous timed automata
- Layered memory automata: recognizers for quasi-regular languages with unbounded memory
- Nondeterministic and co-nondeterministic implies deterministic, for data languages
- Regular expressions for data words
- Reachability in pushdown register automata
- Complexity results on register context-free grammars and related formalisms
- Decision Problems for Finite Automata over Infinite Algebraic Structures
- scientific article; zbMATH DE number 459363 (Why is no real title available?)
- Parametrized automata simulation and application to service composition
- Polynomial-time equivalence testing for deterministic fresh-register automata
- The containment problem for unambiguous register automata
- Fundamentals of Computation Theory
- \(\mathbb {N}\)-memory automata over the alphabet \(\mathbb {N}\)
- scientific article; zbMATH DE number 3057871 (Why is no real title available?)
- Optimal run problem for weighted register automata
- A taxonomy and reductions for common register automata formalisms
- Set augmented finite automata over infinite alphabets
- Active learning for deterministic bottom-up nominal tree automata
- On-the-fly bisimilarity checking for fresh-register automata
- $$\textsc {Reach}$$ on Register Automata via History Independence
- Automata and grammars for data words
- Complexity of membership and non-emptiness problems in unbounded memory automata
- Bisimilarity in fresh-register automata
- Register automata with permutations
- On notions of regularity for data languages
- Decision problems for Turing machines
This page was built for publication: Intractability of decision problems for finite-memory automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1575908)
