Variations on the Common Subexpression Problem
From MaRDI portal
Publication:3908476
DOI10.1145/322217.322228zbMath0458.68026OpenAlexW2000346568MaRDI QIDQ3908476
Peter J. Downey, Ravi Sethi, Robert Endre Tarjan
Publication date: 1980
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322217.322228
graph algorithmrelational databasedecision procedurecongruence closurelossless joinuniform word problemexpression equivalence
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Information storage and retrieval of data (68P20) Theory of operating systems (68N25) Discrete mathematics in relation to computer science (68R99)
Related Items (74)
XML compression via directed acyclic graphs ⋮ Uniqueness of Normal Forms for Shallow Term Rewrite Systems ⋮ Deciding confluence of certain term rewriting systems in polynomial time ⋮ The map equality domain ⋮ Tree automata for code selection ⋮ Congruence Closure of Compressed Terms in Polynomial Time ⋮ Grammar-Based Tree Compression ⋮ An algebraic semantics approach to the effective resolution of type equations ⋮ Satisfiability Modulo Theories ⋮ Efficient ground completion ⋮ Incremental techniques for efficient normalization of nonlinear rewrite systems ⋮ Fast algorithms for testing unsatisfiability of ground Horn clauses with equations ⋮ A semantic approach to optimize linear datalog programs ⋮ Generalizations of algorithms that find invariant relationships in programs over algebra of terms ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Unnamed Item ⋮ Iterative methods of program analysis ⋮ Algorithms for minimization of finite acyclic automata and pattern matching in terms ⋮ Fast congruence closure and extensions ⋮ On the relationship of congruence closure and unification ⋮ Size-optimal top dag compression ⋮ Purging in an equality data base ⋮ NP-completeness of small conflict set generation for congruence closure ⋮ Binary jumbled pattern matching on trees and tree-like structures ⋮ Complexity, convexity and combinations of theories ⋮ A new probabilistic constraint logic programming language based on a generalised distribution semantics ⋮ Typed path polymorphism ⋮ A rewriting approach to satisfiability procedures. ⋮ Modularity and Combination of Associative Commutative Congruence Closure Algorithms enriched with Semantic Properties ⋮ Computing all subtree repeats in ordered trees ⋮ Semantically-guided goal-sensitive reasoning: decision procedures and the Koala prover ⋮ Encoding trees by linear recurrence sequences ⋮ On rewriting rules in Mizar ⋮ Mining approximate patterns with frequent locally optimal occurrences ⋮ Decision procedures for term algebras with integer constraints ⋮ On the computational complexity of cardinality constraints in relational databases ⋮ Transformation synthesis of efficient algorithms with auxiliary specifications ⋮ Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems ⋮ Rigid E-unification: NP-completeness and applications to equational matings ⋮ Fast algorithms for finding a minimum repetition representation of strings and trees ⋮ Conditional congruence closure over uninterpreted and interpreted symbols ⋮ E-generalization using grammars ⋮ Symbol different term rewrite systems ⋮ Tight Bounds for Top Tree Compression ⋮ Using multiset discrimination to solve language processing problems without hashing ⋮ Natural language syntax and first-order inference ⋮ On Shostak's decision procedure for combinations of theories ⋮ Single-valuedness of tree transducers is decidable in polynomial time ⋮ Another variation on the common subexpression problem ⋮ From Search to Computation: Redundancy Criteria and Simplification at Work ⋮ A language for generic programming in the large ⋮ On finding common subtrees ⋮ Automata-driven efficient subterm unification ⋮ Unnamed Item ⋮ Order-Sorted Rewriting and Congruence Closure ⋮ Compressed range minimum queries ⋮ Asymptotic enumeration of compacted binary trees of bounded right height ⋮ A fast algorithm for constructing a tree automaton recognizing a congruential tree language ⋮ Learning from Łukasiewicz and Meredith: investigations into proof structures ⋮ Extending SMT solvers to higher-order logic ⋮ Top tree compression of tries ⋮ Computing congruent closures on terms ⋮ The tree equivalence of linear recursion schemes ⋮ Combination of convex theories: modularity, deduction completeness, and explanation ⋮ Deciding the word problem for ground and strongly shallow identities w.r.t. extensional symbols ⋮ Deciding the word problem for ground identities with commutative and extensional symbols ⋮ Partial derivative automaton by compressing regular expressions ⋮ Algorithms and reductions for rewriting problems. II. ⋮ Deduction, Strategies, and Rewriting ⋮ CC(X): Semantic Combination of Congruence Closure with Solvable Theories ⋮ A linear time solution to the single function coarsest partition problem ⋮ Tree compression with top trees ⋮ Slowing Down Top Trees for Better Worst-Case Compression ⋮ Supercharging plant configurations using Z3
This page was built for publication: Variations on the Common Subexpression Problem
