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

DOI10.1016/0304-3975(76)90065-7MaRDI QIDQ1237361zbMATH OpenOpenAlexFDO

Authors 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

• scientific article; zbMATH DE number 3458598 (Why is no real title available?)
• scientific article; zbMATH DE number 3454792 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• scientific article; zbMATH DE number 3083488 (Why is no real title available?)
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Classes of Predictably Computable Functions
• Subrecursiveness: Machine-independent notions of computability in restricted time and storage
• Writing pushdown acceptors

Cited in

(5)

• Some observations on the connection between counting and recursion
• A note on the relation between polynomial time functionals and Constable's class \(\mathcal K\)
• 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)