Formal Reductions of the General Combinatorial Decision Problem

Cited in

(only showing first 100 items - show all)

The complexity of small universal Turing machines: A survey
Turing oracle machines, online computing, and three displacements in computability theory
Minimality in template-guided recombination
Novikov's centrally symmetric group
A universal machine without change of state
Unsolvable algorithmic problems for semigroups, groups and rings
Herbrand strategies and the greater deducibility relation
Calculi with monotone deductions and their economic interpretation
Deduction search in calculi of general type
Probabilistic canonical calculi
Macroevolution as deduction process
Cut-type rules for calculi of general type
On the universality of Post and splicing systems
Computationalism
The never-ending recursion
Decision problems for semi-Thue systems with a few rules
Context free normal systems and ETOL systems
Computational power of two stacks with restricted communication
Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors
An automated approach to the Collatz conjecture
Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi
Mathematics as information compression via the matching and unification of patterns
Polarization: a new communication protocol in networks of bio-inspired processors
Undecidable iterative propositional calculus
Tag systems and lag systems
Tag systems and Collatz-like functions
Computing by commuting.
Generating and accepting P systems with minimal left and right insertion and deletion
The Complexity of Small Universal Turing Machines: A Survey
Pseudorecursive varieties of semigroups. II
Formalism and intuition in computability
From Turing machines to computer viruses
Small universal devices
Pāṇini's Grammar and Modern Computation
Rules for subatomic derivation
Many-one degrees associated with problems of tag
Formal systems of constructive mathematics
Logical reflection and formalism
Extended Canonical Systems
Why post did [not] have Turing's thesis
KNOWLEDGE REPRESENTATION: A SURVEY OF ITS MECHANISMS, A SKETCH OF ITS SEMANTICS
Closing the Circle: An Analysis of Emil Post's Early Work
Comparison of basic language generating devices (non-deterministic systems)
PROBLEMS WITH COMPLEXITY IN GOLD'S PARADIGM OF INDUCTION Part I: Dynamic Complexity
An Infinite Automaton Characterization of Double Exponential Time
A Natural Axiomatization of Computability and Proof of Church's Thesis
The categorical and the hypothetical: a critique of some fundamental assumptions of standard semantics
Composition of relational productions for plans and programs
Halteprobleme von Fang-Systemen (tag systems)
scientific article; zbMATH DE number 3696535 (Why is no real title available?)
Pure grammars and pure languages†
The theory of recursive functions, approaching its centennial
Herbrand semantics, the potential infinite, and ontology-free logic
A bound on the length of a random derivation-search tree in general multi-premise calculi
Some post canonical systems in one letter
scientific article; zbMATH DE number 3514943 (Why is no real title available?)
Combinatorial systems defined over one- and two-letter alphabets
The work of Kurt Gödel
Programs, Grammars and Arguments: A Personal View of some Connections between Computation, Language and Logic
On the mathematical foundations of \textit{Syntactic structures}
Conceptual Confluence in 1936: Post and Turing
Why Turing’s Thesis Is Not a Thesis
A personal account of Turing's imprint on the development of computer science
Recursive unsolvability of a problem of Thue
Maurice Margenstern's contributions to the field of small universal Turing machines
Non-preserving accepting splicing systems
Fine-Grained Reductions from Approximate Counting to Decision
Average-Case Completeness in Tag Systems
scientific article; zbMATH DE number 7561759 (Why is no real title available?)
Queue Automata: Foundations and Developments
On the computational power of networks of polarized evolutionary processors
Variants of Networks of Evolutionary Processors with Polarizations and a Small Number of Processors
The developments of the concept of machine computability from 1936 to the 1960s
Regular canonical systems
On Post's canonical systems
Undecidability of consequence relation in full non-associative Lambek calculus
An Artificial Chemistry for Networking
Monogenic normal systems are universal
Zur Stufenreduktion von Kalkülen
The post correspondence problem
The equivalence of some general combinatorial decision problems
A Note on Pushdown Store Automata and Regular Systems
Functions with local state: regularity and undecidability
Canonical systems which produce periodic sets
On some metamathematical results as properties of general systems
The Solvability of the Derivability Problem for One-Normal Systems
The many-one equivalence of some general combinatorial decision problems
Decision problems for tag systems
Computability and Recursion
Non-deterministic structures of computation
A representation theorem of infinite dimensional algebras and applications to language theory
A variant of a recursively unsolvable problem
Multiple splicing systems and the universal computability
Logical string rewriting
On a finitary version of mathematical analysis
Mutation calculi
Small networks of polarized splicing processors are universal
An automated approach to the Collatz conjecture
On the complex behavior of simple tag systems -- an experimental approach
A cellular automaton for blocking queen games

This page was built for publication: Formal Reductions of the General Combinatorial Decision Problem

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