The role of rudimentary relations in complexity theory

DOI10.24033/MSMF.311MaRDI QIDQ3347299zbMATH OpenOpenAlexFDO

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, https://eudml.org/doc/94849

zbMATH Keywords

complexity classesalternating Turing machinesrudimentary relationsrudimentary languagesexponential quantification

Mathematics Subject Classification ID

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

Recommendations

• Rudimentary relations and primitive recursion: A toolbox
• On the complexity of computation of rudimentary predicates
• Rudimentary Languages and Second‐Order Logic
• scientific article; zbMATH DE number 704020
• Counting modulo finite semigroups

Cites work

• scientific article; zbMATH DE number 3890734 (Why is no real title available?)
• scientific article; zbMATH DE number 3817701 (Why is no real title available?)
• scientific article; zbMATH DE number 3825168 (Why is no real title available?)
• scientific article; zbMATH DE number 3758312 (Why is no real title available?)
• scientific article; zbMATH DE number 3786751 (Why is no real title available?)
• scientific article; zbMATH DE number 3606443 (Why is no real title available?)
• scientific article; zbMATH DE number 3609651 (Why is no real title available?)
• scientific article; zbMATH DE number 3226635 (Why is no real title available?)
• scientific article; zbMATH DE number 3353257 (Why is no real title available?)
• Alternation
• Complete sets and the polynomial-time hierarchy
• Concatenation as a basis for arithmetic
• Context-free languages and rudimentary attributes
• Quasi-realtime languages
• Rudimentary Predicates and Relative Computation
• Rudimentary interpretation of two-tape turing computation
• Rudimentary relations and stack languages
• Space-bounded reducibility among combinatorial problems
• Stack languages and log n space
• The bounded arithmetic hierarchy
• The complexity of logical theories
• The polynomial-time hierarchy
• Theory of Formal Systems. (AM-47)
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories

Cited in

(3)

• Counting modulo finite semigroups
• Rudimentary reductions revisited
• scientific article; zbMATH DE number 704020 (Why is no real title available?)

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)