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
A rewriting framework and logic for activities subject to regulations
Spectra and satisfiability for logics with successor and a unary function
Counter machines and counter languages
Counter machines and verification problems.
The undecidability of the disjunction property of propositional logics and other related problems
Multi-stack-counter languages
The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors
Normality and automata
Formal analysis of oscillatory behaviors in biological regulatory networks: an alternative approach
Decision problems for pushdown threads
Undecidability in diagonalizable algebras
Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I
P systems with symport/antiport simulating counter automata
Closing the Circle: An Analysis of Emil Post's Early Work
Complexity of some problems in Petri nets
Linear logic as a logic of computations
Remarks on the complexity of nondeterministic counter languages
The Boolean algebra of logic
\(\mathcal C\)-graph automatic groups.
Instruction sequence processing operators
On the universe, disjointness, and containment problems for simple machines
Decidability questions for insertion systems and related models
Decision problems for propositional linear logic
Applying abstract acceleration to (co-)reachability analysis of reactive programs
A decidability result for the model checking of infinite-state systems
Computation with finite stochastic chemical reaction networks
The theory of languages
Typability and type checking in System F are equivalent and undecidable
Complexity and decidability for chain code picture languages
Undecidable properties of extensions of the logic of provability
The theory of languages
Mutation calculi
What makes some language theory problems undecidable
Characterizations of the decidability of some problems for regular trace languages
Looking at mean-payoff and total-payoff through windows
Catalytic P systems, semilinear sets, and vector addition systems
Counting Time in Computing with Cells
Remarks on blind and partially blind one-way multicounter machines
Petri nets, Horn programs, linear logic and vector games
Decidability of code properties
ON ONE-MEMBRANE P SYSTEMS OPERATING IN SEQUENTIAL MODE
When ambients cannot be opened
On incomparable abstract family of languages (AFL)
A survey of state vectors
The conformon-P system: a molecular and cell biology-inspired computability model
NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES
On the complex behavior of simple tag systems -- an experimental approach
Algorithmic properties of structures
Reachability in Succinct and Parametric One-Counter Automata
An undecidable problem in correspondence theory
Simple counter machines and number-theoretic problems
Isomorphisms of scattered automatic linear orders
On the determinacy problem for two-way pushdown automata
The Complexity of Small Universal Turing Machines: A Survey
Domain-free \(\lambda\mu\)-calculus
Low dimensional hybrid systems -- decidable, undecidable, don't know
The stability of the deterministic Skorokhod problem is undecidable
Narrowing based procedures for equational disunification
Parallel communicating grammar systems: the context-sensitive case
The submonoid and rational subset membership problems for graph groups.
Problems concerning fairness and temporal logic for conflict-free Petri nets
On synchronized multi-tape and multi-head automata
Sufficient-completeness, ground-reducibility and their complexity
The undecidability of the Turing machine immortality problem
New decidability results concerning two-way counter machines and applications
Inclusion is undecidable for pattern languages
The complexity of the word problems for commutative semigroups and polynomial ideals
Bad news on decision problems for patterns
On information invariants in robotics
The complexity of decision problems for finite-turn multicounter machines
Deciding reachability problems in Turing-complete fragments of Mobile Ambients
One-way probabilistic reversible and quantum one-counter automata.
Confusion of memory
Tag systems and lag systems
The complexity of small universal Turing machines: A survey
An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
Dynamical systems in categories
Further remarks on DNA overlap assembly
Counter machines, Petri nets, and consensual computation
Tag systems and Collatz-like functions
Undecidability of ground reducibility for word rewriting systems with variables
The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
The word problem and the isomorphism problem for groups
Diem-Grade Logischer Entscheidungsprobleme
Alternation in simple devices
Iterated uniform finite-state transducers on unary languages
Parsimonious computational completeness
Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen
On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
The complexity of finding SUBSEQ\((A)\)
On two-way FA with monotonic counters and quadratic Diophantine equations
A dynamical system which must be stable whose stability cannot be proved
Title not available (Why is that?)
Transductions and the parallel generation of languages^†
Algorithmic Analysis of Array-Accessing Programs
Alternating two-way AC-tree automata
Pushdown automata with reversal-bounded counters
Unsolvable algorithmic problems for semigroups, groups and rings

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)