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

DOI10.1016/0304-3975(76)90065-7zbMath0355.68056OpenAlexW2068422009MaRDI QIDQ1237361

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

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

Related Items (4)

Some formal results about stratificational grammars and their relevance to linguistics ⋮ Some observations on the connection between counting and recursion ⋮ Computation models and function algebras ⋮ Machine-independent description of certain machine complexity classes

Cites Work

• Writing pushdown acceptors
• Classes of Predictably Computable Functions
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Subrecursiveness: Machine-independent notions of computability in restricted time and storage
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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