Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines

Cited in

(only showing first 100 items - show all)

On the computational complexity of membrane systems
Reachability problems and abstract state spaces for time Petri nets with stopwatches
The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
Minsky Machines and Algorithmic Problems
Input-driven multi-counter automata
The undecidability of the first-order theories of one step rewriting in linear canonical systems
Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi
The word problem and the isomorphism problem for groups
Diem-Grade Logischer Entscheidungsprobleme
A rewriting framework and logic for activities subject to regulations
Das Entscheidungsproblem der Klasse von Formeln, die höchstens zwei Primformeln enthalten
Iterated uniform finite-state transducers on unary languages
Parsimonious computational completeness
Spectra and satisfiability for logics with successor and a unary function
Alternation in simple devices
Counter machines and verification problems.
On composition and lookahead delegation of \(e\)-services modeled by automata
On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
The undecidability theorem for the Horn-like fragment of linear logic (revisited)
Counter machines
\(\forall \exists^{5}\)-equational theory of context unification is undecidable
The ^2 fragment of the first-order theory of atomic set constraints is _1⁰-hard
The undecidability of the disjunction property of propositional logics and other related problems
Counter machines and counter languages
On the decision problem for MELL
Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen
Multi-stack-counter languages
Normality and automata
On simulating Turing machines with matrix semigroups with integrality tests
The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors
Generalized planning as heuristic search: a new planning search-space that leverages pointers over objects
The developments of the concept of machine computability from 1936 to the 1960s
The complexity of finding SUBSEQ(A)
Formal analysis of oscillatory behaviors in biological regulatory networks: an alternative approach
MOST SIMPLE EXTENSIONS OF ARE UNDECIDABLE
Finite degree clones are undecidable
Decision problems for pushdown threads
Cut-type rules for calculi of general type
System NEL is undecidable
Undecidability in diagonalizable algebras
P systems with symport/antiport simulating counter automata
Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I
On reachability and safety in infinite-state systems
On two-way FA with monotonic counters and quadratic Diophantine equations
Modeling multitape Minsky and Turing machines by three-tape Minsky machines
A dynamical system which must be stable whose stability cannot be proved
Comparison of max-plus automata and joint spectral radius of tropical matrices
A technique for proving decidability of containment and equivalence of linear constraint queries
On the containment and equivalence problems for GSMs, transducers, and linear CFGs
Complexity of some problems in Petri nets
Closing the Circle: An Analysis of Emil Post's Early Work
Linear logic as a logic of computations
Pushdown automata with reversal-bounded counters
Unsolvable algorithmic problems for semigroups, groups and rings
Alternating two-way AC-tree automata
Algorithmic Analysis of Array-Accessing Programs
Transductions and the parallel generation of languages^†
On Affine Reachability Problems
C-graph automatic groups.
scientific article; zbMATH DE number 2114479 (Why is no real title available?)
Remarks on the complexity of nondeterministic counter languages
Instruction sequence processing operators
On the universe, disjointness, and containment problems for simple machines
One-reversal counter machines and multihead automata: revisited
On two-way weak counter machines
The Boolean algebra of logic
RESTRICTED SETS OF TRAJECTORIES AND DECIDABILITY OF SHUFFLE DECOMPOSITIONS
Expressing additives using multiplicatives and subexponentials
One-reversal counter machines and multihead automata: revisited
Bad News on Decision Problems for Patterns
Decision problems for propositional linear logic
Percentile queries in multi-dimensional Markov decision processes
A note on some systems of lindenmayer
Decidability questions for insertion systems and related models
SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS
Maurice Margenstern's contributions to the field of small universal Turing machines
Accepting runs in a two-way finite automaton
Applying abstract acceleration to (co-)reachability analysis of reactive programs
A decidability result for the model checking of infinite-state systems
Solvable problems for transformers with reversal-bounded counters
On the complexity of decision problems for some classes of machines and applications
Computation with finite stochastic chemical reaction networks
Linear logic automata
Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations
On the complexity of decision problems for counter machines with applications to coding theory
Reachability relations of timed pushdown automata
The theory of languages
Reasoning about reversal-bounded counter machines
Quantum versus deterministic counter automata
Typability and type checking in System F are equivalent and undecidable
Communication for alternating machines
Undecidable properties of extensions of the logic of provability
Complexity and decidability for chain code picture languages
Monogenic normal systems are universal
Mutation calculi
ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS
On the ambiguity and finite-valuedness problems in acceptors and transducers
Theoretical computer science: computability, decidability and logic
Weak cost register automata are still powerful
Indirect addressing and the time relationships of some models of sequential computation

This page was built for publication: Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines

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