On the computational complexity of P automata
DOI10.1007/S11047-005-4461-1zbMATH Open1112.68057OpenAlexW2094727449MaRDI QIDQ876857FDOQ876857
Authors: Erzsébet Csuhaj-Varjú, Oscar H. Ibarra, György Vaszil 
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
Recommendations
- DNA Computing
- On the power of P automata
- On the Computational Complexity of Partial Word Automata Problems
- On a class ofPautomata
- scientific article; zbMATH DE number 1701356
- Complexity of some problems from the theory of automata
- On the power of P and dP automata
- P automata: concepts, results, and new aspects
- On computational complexity of set automata
- On computational complexity of set automata
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 (26)
- Computability by finite automata and pisot bases
- DNA Computing
- 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 the parallelizability of languages accepted by P automata
- On computational complexity of set automata
- Title not available (Why is that?)
- P and dP automata: a survey
- Title not available (Why is that?)
- The complexity of compressed membership problems for finite automata
- P Automata: Membrane Systems as Acceptors
- P automata revisited
- Membrane Computing
- Complexity of some problems from the theory of automata
- The Complexity of Mean-Payoff Automaton Expression
- P automata with restricted power
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)
