On the computational complexity of P automata

DOI10.1007/S11047-005-4461-1MaRDI QIDQ876857zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

automatacontext-sensitive languagescommunicating systemsaccepting systemssub-logarithmic space complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

Cites work

• scientific article; zbMATH DE number 2040914 (Why is no real title available?)
• On a class ofPautomata
• On the computational complexity of membrane systems
• The power of communication: P systems with symport/antiport
• Turing machines with restricted memory access

Cited in

(28)

• Theory of reaction automata: a survey
• Finite dP Automata versus Multi-head Finite Automata
• Computability by finite automata and pisot bases
• DNA Computing
• P colonies. Survey
• The computational capability of chemical reaction automata
• On languages of P automata
• On a class ofPautomata
• Membrane Computing
• On the Computational Complexity of Partial Word Automata Problems
• On the properties of language classes defined by bounded reaction automata
• On The Space Complexity Of Turn Bounded Pushdown 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
• P and dP automata: a survey
• scientific article; zbMATH DE number 7298596 (Why is no real title available?)
• scientific article; zbMATH DE number 1927559 (Why is no real title available?)
• The complexity of compressed membership problems for finite automata
• P Automata: Membrane Systems as Acceptors
• On the power of P automata
• 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)