Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems

DOI10.1016/j.tcs.2006.03.003zbMath1097.68060OpenAlexW2031812378MaRDI QIDQ2503275

Oscar H. Ibarra, Gheorghe Păun

Publication date: 14 September 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.03.003

zbMATH Keywords

systemcontext-sensitive languagesymport/antiportlinear-bounded automatonone-way \(n\) space-bounded Turing machinetwo-way multihead finite automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Computing with cells: membrane systems – some complexity issues ⋮ On the properties of language classes defined by bounded reaction automata ⋮ P AND dP AUTOMATA: UNCONVENTIONAL VERSUS CLASSICAL AUTOMATA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The power of communication: P systems with symport/antiport
• The method of forced enumeration for nondeterministic automata
• Computing with membranes
• A guide to membrane computing.
• Membrane computing. An introduction.
• A note on multihead automata and context-sensitive languages
• On determinism versus nondeterminism in P systems
• On Bounded Symport/Antiport P Systems
• Nondeterministic Space is Closed under Complementation
• A Hierarchy Theorem for Polynomial-Space Recognition
• DNA Computing
• Membrane Computing
• Membrane Computing
• Membrane Computing

This page was built for publication: Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems