Variations on the Common Subexpression Problem

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

Cited in

(82)

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