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 programs; halting problem; complexity problems; structured logic programming

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q60: Specification and verification (program logics, model checking, etc.)

68T99: Artificial intelligence

03D15: Complexity of computation (including implicit computational complexity)

68Q42: Grammars and rewriting systems

68N17: Logic programming

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item