On the computational complexity of P automata
From MaRDI portal
Publication:876857
DOI10.1007/s11047-005-4461-1zbMath1112.68057MaRDI QIDQ876857
Oscar H. Ibarra, Erzsébet Csuhaj-Varjú, 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
automata; context-sensitive languages; communicating systems; accepting systems; sub-logarithmic space complexity
68Q45: Formal languages and automata
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
On the properties of language classes defined by bounded reaction automata, P automata revisited, Finite dP Automata versus Multi-head Finite Automata, P and dP Automata: A Survey, P Automata: Membrane Systems as Acceptors
Cites Work