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)

Full work available at URL https://doi.org/10.1142/S0129054199000198

zbMATH Keywords

acceptance mechanismscomputational complexitycounting-based computationquery orderself-specifying machines

Mathematics Subject Classification ID

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

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 balanced versus unbalanced computation trees
• On Sets with Efficient Implicit Membership Tests
• On the construction of parallel computers from various basis of Boolean functions
• On the power of parity polynomial time
• On the unique satisfiability problem
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
• Qualitative relativizations of complexity classes
• Quantitative Relativizations of Complexity Classes
• Query Order
• Reductions on NP and p-selective sets
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Some observations on the connection between counting and recursion
• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• 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)

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

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)