Intractability of decision problems for finite-memory automata
From MaRDI portal
Publication:1575908
DOI10.1016/S0304-3975(99)00105-XzbMath0952.68080WikidataQ128090046 ScholiaQ128090046MaRDI QIDQ1575908
Hiroshi Sakamoto, Daisuke Ikeda
Publication date: 23 August 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (16)
On notions of regularity for data languages ⋮ Reachability in pushdown register automata ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Complexity results on register context-free grammars and related formalisms ⋮ 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 ⋮ An algebraic characterization of deterministic regular languages over infinite alphabets. ⋮ Parametrized automata simulation and application to service composition ⋮ Polynomial-time equivalence testing for deterministic fresh-register automata ⋮ Nondeterministic and co-nondeterministic implies deterministic, for data languages ⋮ Optimal run problem for weighted register automata ⋮ The containment problem for unambiguous register automata and unambiguous timed automata ⋮ The Containment Problem for Unambiguous Register Automata ⋮ Regular expressions for data words
Cites Work
This page was built for publication: Intractability of decision problems for finite-memory automata
