Thue trees

DOI10.1016/S0168-0072(02)00032-5zbMath1020.03039OpenAlexW4212787582MaRDI QIDQ1861534

Leszek Pacholski, Jerzy Marcinkowski

Publication date: 9 March 2003

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0168-0072(02)00032-5

zbMATH Keywords

undecidabilityThue systemsHorn clause implicationone-step rewriting

Mathematics Subject Classification ID

Database theory (68P15) Undecidability and degrees of sets of sentences (03D35) Mechanization of proofs and logical operations (03B35) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Thue and Post systems, etc. (03D03)

Related Items (1)

Converging to the chase -- a tool for finite controllability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subsumption and implication
• Implication of clauses is undecidable
• The undecidability of the semi-unification problem
• Decidability of a portion of the predicate calculus
• Satisfiability of the smallest binary program
• On the undecidability of implications between embedded multivalued database dependencies
• Unsolvable problems for equational theories
• Solvable cases of the decision problem
• Smallest horn clause programs
• The unsolvability of the Gödel class with identity
• The Implication Problem for Functional and Inclusion Dependencies is Undecidable
• On the efficiency of subsumption algorithms
• The decision problem for standard classes
• The decision problem for equational bases of algebras
• Undecidable properties of finite sets of equations
• The decision problem for formulas with a small number of atomic subformulas
• Undecidability of the first order theory of one-step right ground rewriting
• The first-order theory of one step rewriting in linear noetherian systems is undecidable
• Recursive Unsolvability of a problem of Thue
• Encompassment properties and automata with constraints
• More problems in rewriting
• Problems in rewriting III
• The first-order theory of one-step rewriting is undecidable
• The Concept of Weak Substitution in Theorem-Proving
• Decidability of Second-Order Theories and Automata on Infinite Trees

This page was built for publication: Thue trees