A variant of a recursively unsolvable problem
From MaRDI portal
Publication:5845383
DOI10.1090/S0002-9904-1946-08555-9zbMath0063.06329OpenAlexW2116976042WikidataQ56095056 ScholiaQ56095056MaRDI QIDQ5845383
Publication date: 1946
Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1090/s0002-9904-1946-08555-9
Related Items
Deciding confluence for a simple class of relational transducer networks, Gröbner-Shirshov bases for some Lie algebras, Undecidable iterative propositional calculus, Satisfiability of the smallest binary program, A temporal logic for asynchronous hyperproperties, Parsimonious computational completeness, Variations on the post correspondence problem for free groups, Database survivability under dynamic constraints, Successful visual human-computer interaction is undecidable, Extension of the decidability of the marked PCP to instances with unique blocks, On fixed points of rational transductions, On the decidability of semigroup freeness, Undecidability of infinite post correspondence problem for instances of size 8, Flatwords and Post Correspondence Problem, Projection of object histories, The \$-calculus process algebra for problem solving: A paradigmatic shift in handling hard computational problems, String assembling systems: comparison to sticker systems and decidability, Improved matrix pair undecidability results, A note on controllability of deterministic context-free~systems, On dynamic topological and metric logics, Unsolvable algorithmic problems for semigroups, groups and rings, The origins of combinatorics on words, Pseudoknot-generating operation, Unification in sort theories and its applications, New proof for the undecidability of the circular PCP, The complexity of fuzzy \(\mathcal{EL}\) under the Łukasiewicz t-norm, On a generalization of abelian equivalence and complexity of infinite words, Decidability and complexity for quiescent consistency and its variations, Superdeterministic DPDAs: The method of accepting does affect decision problems, A Confluent Rewriting System Having No Computable, One-Step, Normalizing Strategy, A temporal logic for real-time partial ordering with named transactions, The first-order theory of lexicographic path orderings is undecidable, Decidability of involution hypercodes, On the existence and decidability of unique decompositions of processes in the applied \(\pi\)-calculus, Multiparty half-duplex systems and synchronous communications, On the expressiveness and decidability of higher-order process calculi, Weighted picture automata and weighted logics, Recognizability of the support of recognizable series over the semiring of the integers is undecidable, An optimal quantum error-correcting procedure using quantifier elimination, Decidability of the binary infinite Post Correspondence Problem, Conjunctive query containment over trees using schema information, Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting), Equalizers and kernels in categories of monoids, Complexity and decidability for restricted classes of picture languages, Asymptotic Density and the Theory of Computability: A Partial Survey, An algorithm deciding functional equivalence in a new class of program schemes, GENERALIZED POST CORRESPONDENCE PROBLEM FOR MARKED MORPHISMS, The (generalized) Post correspondence problem with lists consisting of two words is decidable, First-order concatenation theory with bounded quantifiers, A personal account of Turing's imprint on the development of computer science, The Post correspondence problem over a unary alphabet, The decidability of verification under PS 2.0, Periodicity forcing words, On the \(n\)-permutation Post correspondence problem, GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS, A framework for developing stand-alone certifiers, On the decidability of subtyping with bounded existential types and implementation constraints, More decidable instances of Post's correspondence problem: beyond counting, On first-order logic and CPDA graphs, Pseudo-inversion: closure properties and decidability, The unambiguity of segmented morphisms, A new method for undecidability proofs of first order theories, Weak bisimilarity and regularity of context-free processes is EXPTIME-hard, Decidability of operation problems for T0L languages and subclasses, Post correspondence problem for short words, Weighted automata on infinite words in the context of attacker-defender games, Ambiguity in the developmental systems of Lindenmayer, On Post correspondence problem for letter monotonic languages, A useful device for showing the solvability of some decision problems, UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES, On transitive modal many-valued logics, The limits of decidability in fuzzy description logics with general concept inclusions, ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS, On complete one-way functions, Rectangular tileability and complementary tileability are undecidable, Reachability problems in low-dimensional nondeterministic polynomial maps over integers, Some definitional suggestions for automata theory, REDUCTION TREE OF THE BINARY GENERALIZED POST CORRESPONDENCE PROBLEM, Synthesis from hyperproperties, Über einen Automaten mit Pufferspeicherung, Parallel program schemata, The first-order theory of linear one-step rewriting is undecidable, Tetris and decidability, Call-by-value lambda calculus as a model of computation in Coq, On program schemata equivalence, The equivalence problem for deterministic TOL-systems is undecidable, Context-sensitive fusion grammars and fusion grammars with forbidden context are universal, Ambiguity and decision problems for local adjunct languages, Existence of graphs with a given set of r-neighborhoods, On binary equality sets and a solution to the test set conjecture in the binary case, Insertion languages, On the decidability status of fuzzy \(\mathcal {A}\mathcal {L}\mathcal {C}\) with general concept inclusions, Relative undecidability in term rewriting. I: The termination hierarchy, Relative undecidability in term rewriting. II: The confluence hierarchy, Hilbert's tenth problem for term algebras with a substitution operator, Unambiguous injective morphisms in free groups, Modelization of deterministic rational relations, Binary (generalized) Post Correspondence Problem, Undecidable Properties on Length-Two String Rewriting Systems, On simplest possible solutions for Post Correspondence Problems, The theory of languages, The post correspondence problem, The equivalence of some general combinatorial decision problems, PCP-prime words and primality types, Distributed Asynchronous Games With Causal Memory are Undecidable, Automatic sequences of rank two, On CD-Systems of Stateless Deterministic Two-Phase RR(1)-Automata, Ambiguity of Morphisms in a Free Group, On the Undecidability of Fuzzy Description Logics with GCIs and Product T-norm, UNDECIDABILITY AND NON-AXIOMATIZABILITY OF MODAL MANY-VALUED LOGICS, Generalizations of Code Languages with Marginal Errors, OVERLAP-FREE LANGUAGES AND SOLID CODES, The first-order theory of one-step rewriting is undecidable, Unsolvability in 3 × 3 Matrices, Unnamed Item, The theory of languages, Normal forms for phrase-structure grammars, Weighted Automata on Infinite Words in the Context of Attacker-Defender Games, Rational, recognizable, and aperiodic partially lossy queue languages, The many-one equivalence of some general combinatorial decision problems, A temporal logic for real-time partial-ordering with named transactions, The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups, On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus, Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width, Constructive Many-one Reduction from the Halting Problem to Semi-unification (Extended Version), Robustness against Read Committed for Transaction Templates with Functional Constraints, Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time, Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis, Decidability of liveness for concurrent objects on the TSO memory model, Integer Weighted Automata on Infinite Words, Post's correspondence problem: from computer science to algebra, What else is undecidable about loops?, Synchronizing deterministic push-down automata can be really hard, On bi-infinite and conjugate post correspondence problems, Post's Correspondence Problem for hyperbolic and virtually nilpotent groups, Freezing 1-Tag Systems with States, On the Density of Context-Free and Counter Languages, ALGORITHMS FOR THE JOIN AND AUTO-INTERSECTION OF MULTI-TAPE WEIGHTED FINITE-STATE MACHINES, Unnamed Item, Unnamed Item, Large Simple Binary Equality Words, Conceptual Confluence in 1936: Post and Turing, Algorithms: From Al-Khwarizmi to Turing and Beyond, Unnamed Item, Post correspondence problem: Words possible as primitive solutions, Cocyclic subshifts from Diophantine equations, Minimal undecidable identity problem for finite-automaton mappings, Recursed Is Not Recursive: A Jarring Result, A survey of computational complexity results in systems and control, Recursive Unsolvability of a problem of Thue, LARGE SIMPLE BINARY EQUALITY WORDS, Gröbner–Shirshov bases and their calculation, On the Complexity of RSRL, Marked PCP is decidable, Unnamed Item, Unnamed Item, Binary equality words with two $b$'s, Undecidability of Operation Problems for T0L Languages and Subclasses, Tiling the Plane with a Fixed Number of Polyominoes, Generalizations of Code Languages with Marginal Errors, Post Correspondence Problem and Small Dimensional Matrices, Equivalence problem for finitely ambiguous finite automata over semigroups, Reachability via Cooperating Morphisms, UNAMBIGUOUS MORPHIC IMAGES OF STRINGS, ON THE POWER OF COOPERATING MORPHISMS VIA REACHABILITY PROBLEMS, ON THE DUAL POST CORRESPONDENCE PROBLEM, An unsolvable problem with products of matrices, ON REACHABILITY AND SAFETY IN INFINITE-STATE SYSTEMS, Undecidability of infinite post correspondence problem for instances of Size 9, Closing the Circle: An Analysis of Emil Post's Early Work, The word problem and the isomorphism problem for groups
Cites Work
