On the computational complexity of P automata

DOI10.1007/S11047-005-4461-1zbMath1112.68057OpenAlexW2094727449MaRDI QIDQ876857

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

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)

Related Items (9)

Finite dP Automata versus Multi-head Finite Automata ⋮ P Automata: Membrane Systems as Acceptors ⋮ P and dP Automata: A Survey ⋮ Theory of reaction automata: a survey ⋮ On the properties of language classes defined by bounded reaction automata ⋮ P automata revisited ⋮ P colonies. Survey ⋮ The computational capability of chemical reaction automata ⋮ Membrane automata for modeling biomolecular processes

Cites Work

• Unnamed Item
• On the computational complexity of membrane systems
• The power of communication: P systems with symport/antiport
• On a class ofPautomata
• Turing machines with restricted memory access

This page was built for publication: On the computational complexity of P automata