Formal Reductions of the General Combinatorial Decision Problem
From MaRDI portal
Publication:5845381
DOI10.2307/2371809zbMath0063.06327OpenAlexW2326418800WikidataQ56267314 ScholiaQ56267314MaRDI QIDQ5845381
Publication date: 1943
Published in: American Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2371809
Related Items (only showing first 100 items - show all)
Small networks of polarized splicing processors are universal ⋮ A cellular automaton for blocking queen games ⋮ An automated approach to the Collatz conjecture ⋮ On a finitary version of mathematical analysis ⋮ Unnamed Item ⋮ Novikov's centrally symmetric group ⋮ The post correspondence problem ⋮ The equivalence of some general combinatorial decision problems ⋮ Undecidable iterative propositional calculus ⋮ The Complexity of Small Universal Turing Machines: A Survey ⋮ Parsimonious computational completeness ⋮ Canonical systems which produce periodic sets ⋮ PSEUDORECURSIVE VARIETIES OF SEMIGROUPS — II ⋮ A universal machine without change of state ⋮ Herbrand semantics, the potential infinite, and ontology-free logic ⋮ On some metamathematical results as properties of general systems ⋮ Tag systems and lag systems ⋮ The Solvability of the Derivability Problem for One-Normal Systems ⋮ Unsolvable algorithmic problems for semigroups, groups and rings ⋮ A bound on the length of a random derivation-search tree in general multi-premise calculi ⋮ The many-one equivalence of some general combinatorial decision problems ⋮ Mutation calculi ⋮ Comparison of basic language generating devices (non-deterministic systems) ⋮ Formalism and intuition in computability ⋮ From Turing machines to computer viruses ⋮ Many-one degrees associated with problems of tag ⋮ The categorical and the hypothetical: a critique of some fundamental assumptions of standard semantics ⋮ Regular canonical systems ⋮ Small Universal Devices ⋮ On Post's canonical systems ⋮ PROBLEMS WITH COMPLEXITY IN GOLD'S PARADIGM OF INDUCTION Part I: Dynamic Complexity ⋮ On the complex behavior of simple tag systems -- an experimental approach ⋮ The never-ending recursion ⋮ Unnamed Item ⋮ Formal systems of constructive mathematics ⋮ A Note on Pushdown Store Automata and Regular Systems ⋮ Herbrand strategies and the greater deducibility relation ⋮ Queue Automata: Foundations and Developments ⋮ Pāṇini's Grammar and Modern Computation ⋮ Decision problems for tag systems ⋮ Logical reflection and formalism ⋮ Tree search and quantum computation ⋮ On the mathematical foundations of \textit{Syntactic structures} ⋮ Some post canonical systems in one letter ⋮ The immortality problem for Lag systems ⋮ Computational power of two stacks with restricted communication ⋮ Calculi with monotone deductions and their economic interpretation ⋮ Computability and Recursion ⋮ A personal account of Turing's imprint on the development of computer science ⋮ An Infinite Automaton Characterization of Double Exponential Time ⋮ Conceptual Confluence in 1936: Post and Turing ⋮ Why Turing’s Thesis Is Not a Thesis ⋮ Why Post Did [Not Have Turing’s Thesis] ⋮ Programs, Grammars and Arguments: A Personal View of some Connections between Computation, Language and Logic ⋮ Combinatorial systems defined over one- and two-letter alphabets ⋮ On the computational power of networks of polarized evolutionary processors ⋮ Tag systems and Collatz-like functions ⋮ Unnamed Item ⋮ Recursive Unsolvability of a problem of Thue ⋮ Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors ⋮ Small universal accepting hybrid networks of evolutionary processors ⋮ Decision problems for semi-Thue systems with a few rules ⋮ Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi ⋮ Non-deterministic structures of computation ⋮ Deleting string rewriting systems preserve regularity ⋮ Computing by commuting. ⋮ Composition of relational productions for plans and programs ⋮ Multiple splicing systems and the universal computability ⋮ Logical string rewriting ⋮ Functions with local state: regularity and undecidability ⋮ The work of Kurt Gödel ⋮ KNOWLEDGE REPRESENTATION: A SURVEY OF ITS MECHANISMS, A SKETCH OF ITS SEMANTICS ⋮ A representation theorem of infinite dimensional algebras and applications to language theory ⋮ Mathematics as information compression via the matching and unification of patterns ⋮ Halteprobleme von Fang-Systemen (tag systems) ⋮ Deduction search in calculi of general type ⋮ Probabilistic canonical calculi ⋮ Variants of Networks of Evolutionary Processors with Polarizations and a Small Number of Processors ⋮ A Natural Axiomatization of Computability and Proof of Church's Thesis ⋮ The complexity of small universal Turing machines: A survey ⋮ Macroevolution as deduction process ⋮ Cut-type rules for calculi of general type ⋮ Polarization: a new communication protocol in networks of bio-inspired processors ⋮ An automated approach to the Collatz conjecture ⋮ Pure grammars and pure languages† ⋮ RULES FOR SUBATOMIC DERIVATION ⋮ Average-Case Completeness in Tag Systems ⋮ Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines ⋮ Turing oracle machines, online computing, and three displacements in computability theory ⋮ On the universality of Post and splicing systems ⋮ Minimality in template-guided recombination ⋮ Proof search algorithm in pure logical framework ⋮ Context free normal systems and ETOL systems ⋮ A variant of a recursively unsolvable problem ⋮ UNDECIDABILITY OF CONSEQUENCE RELATION IN FULL NON-ASSOCIATIVE LAMBEK CALCULUS ⋮ Computationalism ⋮ An Artificial Chemistry for Networking ⋮ The Developments of the Concept of Machine Computability from 1936 to the 1960s ⋮ Extended Canonical Systems ⋮ Monogenic normal systems are universal
This page was built for publication: Formal Reductions of the General Combinatorial Decision Problem
