The role of rudimentary relations in complexity theory
DOI10.24033/MSMF.311zbMATH Open0558.68043OpenAlexW2261006039MaRDI QIDQ3347299FDOQ3347299
Authors: Hugo Volger 
Publication date: 1984
Published in: Mémoires de la Société mathématique de France (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=MSMF_1984_2_16__41_0
Recommendations
complexity classesalternating Turing machinesrudimentary relationsrudimentary languagesexponential quantification
Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20)
Cites Work
- Title not available (Why is that?)
- Alternation
- The polynomial-time hierarchy
- Quasi-realtime languages
- Theory of Formal Systems. (AM-47)
- The complexity of logical theories
- Complete sets and the polynomial-time hierarchy
- Concatenation as a basis for arithmetic
- Title not available (Why is that?)
- Space-bounded reducibility among combinatorial problems
- Rudimentary Predicates and Relative Computation
- Title not available (Why is that?)
- Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
- Title not available (Why is that?)
- Rudimentary interpretation of two-tape turing computation
- Title not available (Why is that?)
- Context-free languages and rudimentary attributes
- The bounded arithmetic hierarchy
- Stack languages and log n space
- Rudimentary relations and stack languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (3)
This page was built for publication: The role of rudimentary relations in complexity theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3347299)
