SELF-SPECIFYING MACHINES

DOI10.1142/S0129054199000198zbMATH Open1319.68083MaRDI QIDQ5249003FDOQ5249003

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)

Recommendations

• scientific article; zbMATH DE number 1810490
• Self-assembling finite automata
• scientific article; zbMATH DE number 2089986
• Self-assembling pushdown automata
• scientific article
• 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

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)

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• 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
• 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)