Variations on the Common Subexpression Problem

Theory of operating systems (68N25) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99)

Cited in

(85)

Combination of convex theories: modularity, deduction completeness, and explanation
A linear time solution to the single function coarsest partition problem
An algebraic semantics approach to the effective resolution of type equations
Fast algorithms for testing unsatisfiability of ground Horn clauses with equations
On the relationship of congruence closure and unification
Purging in an equality data base
Complexity, convexity and combinations of theories
On the computational complexity of cardinality constraints in relational databases
Natural language syntax and first-order inference
On finding common subtrees
A fast algorithm for constructing a tree automaton recognizing a congruential tree language
Computing congruent closures on terms
Tree automata for code selection
Generalizations of algorithms that find invariant relationships in programs over algebra of terms
A rewriting approach to satisfiability procedures.
The tree equivalence of linear recursion schemes
The map equality domain
NP-completeness of small conflict set generation for congruence closure
Encoding trees by linear recurrence sequences
Conditional congruence closure over uninterpreted and interpreted symbols
Algorithms and reductions for rewriting problems. II.
Deciding confluence of certain term rewriting systems in polynomial time
Computing all subtree repeats in ordered trees
On rewriting rules in Mizar
Learning from Łukasiewicz and Meredith: investigations into proof structures
Top tree compression of tries
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
Supercharging plant configurations using Z3
Asymptotic enumeration of compacted binary trees of bounded right height
Extending SMT solvers to higher-order logic
Tree compression with top trees
Constructing small tree grammars and small circuits for formulas
Size-optimal top dag compression
Typed path polymorphism
Decision procedures for term algebras with integer constraints
Fast algorithms for finding a minimum repetition representation of strings and trees
E-generalization using grammars
XML compression via directed acyclic graphs
Order-Sorted Rewriting and Congruence Closure
Deduction, strategies, and rewriting
\textsf{CC(X)}: semantic combination of congruence closure with solvable theories
Congruence closure of compressed terms in polynomial time
Satisfiability modulo theories
Grammar-Based Tree Compression
Transformation synthesis of efficient algorithms with auxiliary specifications
Iterative methods of program analysis
Algorithms for minimization of finite acyclic automata and pattern matching in terms
Efficient type checking for path polymorphism
On Shostak's decision procedure for combinations of theories
From search to computation: redundancy criteria and simplification at work
Symbol different term rewrite systems
The weight function in the subtree kernel is decisive
Efficient ground completion
Incremental techniques for efficient normalization of nonlinear rewrite systems
Slowing down top trees for better worst-case compression
Tight bounds for top tree compression
Uniqueness of normal forms for shallow term rewrite systems
A language for generic programming in the large
Automata-driven efficient subterm unification
Modularity and Combination of Associative Commutative Congruence Closure Algorithms enriched with Semantic Properties
Semantically-guided goal-sensitive reasoning: decision procedures and the Koala prover
KBO Constraint Solving Revisited
Incremental dead state detection in logarithmic time
The tree equivalence problem for linear recursion schemes
Slowing down top trees for better worst-case compression
Investigations into proof structures
Using multiset discrimination to solve language processing problems without hashing
Single-valuedness of tree transducers is decidable in polynomial time
Another variation on the common subexpression problem
Memoization on shared subtrees accelerates computations on genealogical forests
Asymptotics of relaxed k-ary trees
Computing ground congruence classes
Congruence closure modulo groups
Semantic foundations of equality saturation
Database theory in action: search-based program optimization
Compressed structures for partial derivative automata constructions
A semantic approach to optimize linear datalog programs
Fast congruence closure and extensions
Binary jumbled pattern matching on trees and tree-like structures
A new probabilistic constraint logic programming language based on a generalised distribution semantics
Mining approximate patterns with frequent locally optimal occurrences
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

This page was built for publication: Variations on the Common Subexpression Problem

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