Congruence Closure of Compressed Terms in Polynomial Time

DOI10.1007/978-3-642-24364-6_16zbMath1348.68085OpenAlexW85844715MaRDI QIDQ3172897

Altug Anis, David Sabel, Manfred Schmidt-Schauss

Publication date: 7 October 2011

Published in: Frontiers of Combining Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-24364-6_16

zbMATH Keywords

term rewritinggrammar-based compressioncongruence closuresingleton tree grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Related Items (2)

Grammar-Based Tree Compression ⋮ Approximation of smallest linear tree grammar

Uses Software

• Haskell

Cites Work

• Unnamed Item
• Unnamed Item
• A fast algorithm for generating reduced ground rewriting systems from a set of ground equations
• On the complexity of Bounded Second-Order Unification and Stratified Context Unification
• Unification and matching on compressed terms
• Solving SAT and SAT Modulo Theories
• Processing Compressed Texts: A Tractability Border
• Bounded Second-Order Unification Is NP-Complete
• Stratified Context Unification Is NP-Complete
• Parameter Reduction in Grammar-Compressed Trees
• Fast Decision Procedures Based on Congruence Closure
• Variations on the Common Subexpression Problem
• An algorithm for finding canonical sets of ground rewrite rules in polynomial time
• An algorithm for reasoning about equality
• A universal algorithm for sequential data compression
• Term Rewriting and All That
• First-Order Unification on Compressed Terms
• Word Problems and Membership Problems on Compressed Words
• Database Programming Languages

This page was built for publication: Congruence Closure of Compressed Terms in Polynomial Time