Classes of Recursively Enumerable Sets and Their Decision Problems
From MaRDI portal
Publication:5823276
DOI10.2307/1990888zbMath0053.00301OpenAlexW4249297534WikidataQ54084246 ScholiaQ54084246MaRDI QIDQ5823276
Publication date: 1953
Full work available at URL: https://doi.org/10.2307/1990888
Related Items
The basic theory of partial \(\alpha\)-recursive operators ⋮ Code obfuscation against abstraction refinement attacks ⋮ Productive Sets ⋮ An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ Introduction to Model Checking ⋮ Recursion theorems and effective domains ⋮ Parametric Church's thesis: synthetic computability without choice ⋮ More really is different ⋮ Asymptotic density, immunity and randomness ⋮ Index sets related to prompt simplicity ⋮ An Effective Operator, Continuous but not Partial Recursive ⋮ From undecidability of non-triviality and finiteness to undecidability of learnability ⋮ Looking at Euler flows through a contact mirror: universality and undecidability ⋮ Indexings of subrecursive classes ⋮ Efficient equivalence-checking algorithms for procedural programs in progressive semigroup gateway models ⋮ Fixed-parameter decidability: Extending parameterized complexity analysis ⋮ On the information carried by programs about the objects they compute ⋮ How much partiality is needed for a theory of computability? ⋮ Deciding program properties via complete abstractions on bounded domains ⋮ Parameterized synthesis for fragments of first-order logic over data words ⋮ Edge-label controlled graph grammars ⋮ A complete uniform substitution calculus for differential dynamic logic ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ Unnamed Item ⋮ Decision-procedures for invariant properties of short algorithms ⋮ Computability and the morphological complexity of some dynamics on continuous domains ⋮ Superintelligence Cannot be Contained: Lessons from Computability Theory ⋮ Improving Strategies via SMT Solving ⋮ Connecting Program Synthesis and Reachability: Automatic Program Repair Using Test-Input Generation ⋮ Aggregating inductive expertise on partial recursive functions ⋮ Calculational design of a regular model checker by abstract interpretation ⋮ Non-overlapping inversion on strings and languages ⋮ Rice’s Theorem for μ-Limit Sets of Cellular Automata ⋮ The semilattice of computable families of recursively enumerable sets ⋮ Highly Automated Formal Proofs over Memory Usage of Assembly Code ⋮ Spaces with combinators ⋮ Recursiveness and preference orderings ⋮ Things that can be made into themselves ⋮ Index Sets and Universal Numberings ⋮ A well-structured framework for analysing Petri net extensions ⋮ Index sets in 0' ⋮ What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\) ⋮ Lower bounds and the hardness of counting properties ⋮ Complexity classes of partial recursive functions ⋮ Index sets and universal numberings ⋮ Translating between Language and Logic: What Is Easy and What Is Difficult ⋮ Recognition of invariant properties of algorithms ⋮ Cutting corners ⋮ Some decision problems for polynomial mappings ⋮ A Rice-style theorem for parallel automata ⋮ Introducing complexity to formal testing ⋮ Analogues of Rice's theorem for semantic classes of propositions ⋮ Weakening additivity in adjoining closures ⋮ Recursively enumerable sets and degrees ⋮ Vladimir Andreevich Uspensky (27/11/1930–27/6/2018) ⋮ Some lattice-invariant properties of classes of recursively enumerable sets ⋮ Referenced automata and metaregular families ⋮ Degrees of Computability ⋮ Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian ⋮ COMPLETE ADDITIVITY AND MODAL INCOMPLETENESS ⋮ A second step towards complexity-theoretic analogs of Rice's Theorem ⋮ The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions ⋮ Some Theorems on Classes of Recursively Enumerable Sets ⋮ Unnamed Item ⋮ On an optimal propositional proof system and the structure of easy subsets of TAUT. ⋮ The complexity of universal text-learners. ⋮ Intensional Kleene and Rice theorems for abstract program semantics ⋮ On the Decidability of the Equivalence Problem for Monadic Recursive Programs ⋮ The Physical Meaning of the Holographic Principle ⋮ Subrecursive equivalence relations and (non-)closure under lattice operations
Cites Work
