Weighted graphs: A tool for studying the halting problem and time complexity in term rewriting systems and logic programming

DOI10.1016/0304-3975(90)90066-QzbMath0702.68036MaRDI QIDQ915431

Philippe Devienne

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

logic programshalting problemcomplexity problemsstructured logic programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Artificial intelligence (68T99) Complexity of computation (including implicit computational complexity) (03D15) Grammars and rewriting systems (68Q42) Logic programming (68N17)

Related Items

Satisfiability of the smallest binary program, Reduction of cycle unification of type \(Cpg+r\), Simulation of Turing machines by a regular rewrite rule, Primal grammars and unification modulo a binary clause

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamental properties of infinite trees
• Properties of substitutions and unifications
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• Termination of rewriting
• Simulation of Turing machines by a regular rewrite rule
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Flow diagrams, turing machines and languages with only two formation rules