Congruence closure of compressed terms in polynomial time

DOI10.1007/978-3-642-24364-6_16zbMATH Open1348.68085OpenAlexW85844715MaRDI QIDQ3172897FDOQ3172897

Authors: David Sabel, Altug Anis, Manfred Schmidt-Schauß 

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

Recommendations

• scientific article; zbMATH DE number 58292
• Recompression: word equations and beyond
• Linear pattern matching of compressed terms and polynomial rewriting
• Unification and matching on compressed terms
• Linear compressed pattern matching for polynomial rewriting (extended abstract)

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)

Cites Work

• Title not available (Why is that?)
• Variations on the Common Subexpression Problem
• Solving SAT and SAT modulo theories, from an abstract Davis-Putnam-Logemann-Loveland procedure to \(\operatorname{DPLL}(T)\)
• An algorithm for finding canonical sets of ground rewrite rules in polynomial time
• A universal algorithm for sequential data compression
• Term Rewriting and All That
• Fast Decision Procedures Based on Congruence Closure
• Unification and matching on compressed terms
• Processing Compressed Texts: A Tractability Border
• Title not available (Why is that?)
• Database Programming Languages
• 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
• Bounded Second-Order Unification Is NP-Complete
• Parameter Reduction in Grammar-Compressed Trees
• First-order unification on compressed terms
• Word Problems and Membership Problems on Compressed Words
• Stratified Context Unification Is NP-Complete
• An algorithm for reasoning about equality

Cited In (7)

• Grammar-Based Tree Compression
• Unification with Singleton Tree Grammars
• Computing congruent closures on terms
• Linear compressed pattern matching for polynomial rewriting (extended abstract)
• Approximation of smallest linear tree grammar
• NP-completeness of small conflict set generation for congruence closure
• Linear pattern matching of compressed terms and polynomial rewriting

Uses Software

• Haskell

This page was built for publication: Congruence closure of compressed terms in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3172897)