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)

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
RESTRICTED SETS OF TRAJECTORIES AND DECIDABILITY OF SHUFFLE DECOMPOSITIONS
On two-way weak counter machines
A note on some systems of lindenmayer
Bad News on Decision Problems for Patterns
One-reversal counter machines and multihead automata: revisited
One-reversal counter machines and multihead automata: revisited
On the complexity of decision problems for some classes of machines and applications
Linear logic automata
Reachability relations of timed pushdown automata
Communication for alternating machines
On the ambiguity and finite-valuedness problems in acceptors and transducers
Indirect addressing and the time relationships of some models of sequential computation
From mathesis universalis to provability, computability, and constructivity
Augmenting the discrete timed automaton with other data structures.
Herbrand strategies and the greater deducibility relation
The reachability problem for Petri nets and decision problems for Skolem arithmetic
Existential arithmetization of Diophantine equations
Pushdown automata with counters
About \(P\) systems with symport/antiport
On decision problems for parameterized machines
Undecidability of the identity problem for finite semigroups
What is a universal computing machine?
The complexity of reachability in distributed communicating processes
Decision problems for tag systems
Register machine proof of the theorem on exponential diophantine representation of enumerable sets
Programs, Grammars and Arguments: A Personal View of some Connections between Computation, Language and Logic
The immortality problem for Lag systems
The word and order problems for self-similar and automata groups
Nondecidable intermediate calculus
Time-restricted sequence generation
Semilinearity of families of languages
A characterization of reversal-bounded multipushdown machine languages
Halteprobleme von Fang-Systemen (tag systems)
Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. III
On the overlap assembly of strings and languages
Finite automata with multiplication
Generalizations of Checking Stack Automata: Characterizations and Hierarchies
Two-way deterministic multi-weak-counter machines
On two-way nondeterministic finite automata with one reversal-bounded counter
On the solvability of a class of Diophantine equations and applications
Two-way automata with more than one storage medium
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

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)