On languages specified by relative acceptance

DOI10.1016/0304-3975(78)90048-8zbMath0385.68061OpenAlexW2075402194MaRDI QIDQ1249438

Celia Wrathall, Ronald V. Book

Publication date: 1978

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

Full work available at URL: https://doi.org/10.1016/0304-3975(78)90048-8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Representations of language families by homomorphic equality operations and generalized equality sets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Characterizations of reduction classes modulo oracle conditions ⋮ Reset machines ⋮ Bounded query machines: on NP and PSPACE

Cites Work

• Unnamed Item
• Unnamed Item
• Augmented loop languages and classes of computable functions
• Space-bounded reducibility among combinatorial problems
• A comparison of polynomial time reducibilities
• The polynomial-time hierarchy
• Control sets on context-free grammar forms
• Complete sets and the polynomial-time hierarchy
• One way finite visit automata
• A second step toward the polynomial hierarchy
• The lattices of prefixes and overlaps of traces
• Time- and tape-bounded Turing acceptors and AFLs
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Relativization of questions about log space computability
• Simple Representations of Certain Classes of Languages
• Comparing language operations
• Linear Languages and the Intersection Closures of Classes of Languages
• Rudimentary Predicates and Relative Computation
• The complexity of the membership problem for some extensions of context-free languagest†