The role of rudimentary relations in complexity theory

DOI10.24033/msmf.311zbMath0558.68043OpenAlexW2261006039MaRDI QIDQ3347299

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

zbMATH Keywords

rudimentary relationscomplexity classesalternating Turing machinesrudimentary languagesexponential quantification

Mathematics Subject Classification ID

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

Related Items

Rudimentary reductions revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
• The complexity of logical theories
• Space-bounded reducibility among combinatorial problems
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Stack languages and log n space
• Theory of Formal Systems. (AM-47)
• Alternation
• Rudimentary relations and stack languages
• The bounded arithmetic hierarchy
• Rudimentary Predicates and Relative Computation
• Context-free languages and rudimentary attributes
• Quasi-realtime languages
• Rudimentary interpretation of two-tape turing computation
• Concatenation as a basis for arithmetic