On the computational complexity of P automata
DOI10.1007/S11047-005-4461-1zbMATH Open1112.68057OpenAlexW2094727449MaRDI QIDQ876857FDOQ876857
György Vaszil, Erzsébet Csuhaj-Varjú, Oscar H. Ibarra
Publication date: 19 April 2007
Published in: Natural Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11047-005-4461-1
automatacontext-sensitive languagescommunicating systemsaccepting systemssub-logarithmic space complexity
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
Cited In (23)
- Computability by finite automata and pisot bases
- Theory of reaction automata: a survey
- Finite dP Automata versus Multi-head Finite Automata
- P colonies. Survey
- The computational capability of chemical reaction automata
- Membrane Computing
- On a class ofPautomata
- On the Computational Complexity of Partial Word Automata Problems
- On The Space Complexity Of Turn Bounded Pushdown Automata
- On the properties of language classes defined by bounded reaction automata
- Exact complexity of problems of incompletely specified automata
- Computing the Rabin Index of a Parity Automaton
- Membrane automata for modeling biomolecular processes
- On computational complexity of set automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of compressed membership problems for finite automata
- P Automata: Membrane Systems as Acceptors
- P automata revisited
- P and dP Automata: A Survey
- Complexity of some problems from the theory of automata
- The Complexity of Mean-Payoff Automaton Expression
- P automata with restricted power
Recommendations
- DNA Computing 👍 👎
- On the Power of P Automata 👍 👎
- On the Computational Complexity of Partial Word Automata Problems 👍 👎
- On a class ofPautomata 👍 👎
- Title not available (Why is that?) 👍 👎
- Complexity of some problems from the theory of automata 👍 👎
- Title not available (Why is that?) 👍 👎
- P Automata: Concepts, Results, and New Aspects 👍 👎
- On computational complexity of set automata 👍 👎
- On computational complexity of set automata 👍 👎
This page was built for publication: On the computational complexity of P automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q876857)
