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 (7)

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†

This page was built for publication: On languages specified by relative acceptance