SELF-SPECIFYING MACHINES

DOI10.1142/S0129054199000198MaRDI QIDQ5249003zbMATH OpenFDO

Authors Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung

Publication date 29 April 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexityquery orderacceptance mechanismscounting-based computationself-specifying machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1810490
• Self-assembling finite automata
• scientific article; zbMATH DE number 2089986
• Self-assembling pushdown automata
• scientific article; zbMATH DE number 6528599
• Self-verifying finite automata and descriptional complexity
• Some small self-describing Turing machines
• Self-correcting constructions of finite automata
• Self-modifying finite automata: An introduction

Cites work

• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• A comparison of polynomial time reducibilities
• A complexity theory for feasible closure properties
• A note on parallel queries and the symmetric-difference hierarchy.
• A uniform approach to define complexity classes
• Complexity-Restricted Advice Functions
• Defying upward and downward separation
• Gap-definable counting classes
• Logspace and logtime leaf languages
• On Sets with Efficient Implicit Membership Tests
• On balanced versus unbalanced computation trees
• On the construction of parallel computers from various basis of Boolean functions
• On the power of parity polynomial time
• On the unique satisfiability problem
• PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Qualitative relativizations of complexity classes
• Quantitative Relativizations of Complexity Classes
• Query Order
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Reductions on NP and p-selective sets
• Some observations on the connection between counting and recursion
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• The Complexity of Enumeration and Reliability Problems
• The complexity of computing the permanent
• The complexity of optimization problems
• The power of the middle bit of a \(\#\)P function
• Threshold Computation and Cryptographic Security
• Universally serializable computation

Cited in

(5)

• Self-monitoring machines and an \(\omega^ \omega\) hierarchy of loops
• A second step towards complexity-theoretic analogs of Rice's Theorem
• scientific article; zbMATH DE number 1810490 (Why is no real title available?)
• Query Order
• Some small self-describing Turing machines

This page was built for publication: SELF-SPECIFYING MACHINES

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5249003)