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