A recursive and a grammatical characterization of the exponential-time languages

DOI10.1016/0304-3975(76)90065-7zbMATH Open0355.68056OpenAlexW2068422009MaRDI QIDQ1237361FDOQ1237361

Burkhard Monien

Publication date: 1977

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

Full work available at URL: http://nbn-resolving.de/urn:nbn:de:hbz:466:2-4330

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Writing pushdown acceptors
• Classes of Predictably Computable Functions
• Subrecursiveness: Machine-independent notions of computability in restricted time and storage

Cited In (5)

• A note on the relation between polynomial time functionals and Constable's class \(\mathcal K\)
• Some observations on the connection between counting and recursion
• Computation models and function algebras
• Some formal results about stratificational grammars and their relevance to linguistics
• Machine-independent description of certain machine complexity classes

This page was built for publication: A recursive and a grammatical characterization of the exponential-time languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1237361)