Unification with Singleton Tree Grammars

DOI10.1007/978-3-642-02348-4_26MaRDI QIDQ3636835zbMATH OpenOpenAlexFDO

Authors Adrià Gascón, Guillem Godoy, Manfred Schmidt-Schauß

Publication date 30 June 2009

Published in Rewriting Techniques and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02348-4_26

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Recommendations

• Unification and matching on compressed terms
• First-order unification on compressed terms
• One-context unification with STG-compressed terms is in NP
• Deciding context unification
• Congruence closure of compressed terms in polynomial time

Cites work

• A Machine-Oriented Logic Based on the Resolution Principle
• An Efficient Unification Algorithm
• Bounded Second-Order Unification Is NP-Complete
• Context unification with one context variable
• Database Programming Languages
• Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes
• scientific article; zbMATH DE number 2086239 (Why is no real title available?)
• Parameter Reduction in Grammar-Compressed Trees
• Processing Compressed Texts: A Tractability Border
• Rewriting Techniques and Applications
• Stratified Context Unification Is NP-Complete
• The complexity of tree automata and XPath on grammar-compressed trees
• Unification theory
• Word Problems and Membership Problems on Compressed Words

Cited in

(8)

• On the complexity of the smallest grammar problem over fixed alphabets
• Unification grammars.
• Unidirectional Derivation Semantics for Synchronous Tree-Adjoining Grammars
• scientific article; zbMATH DE number 176239 (Why is no real title available?)
• Parameter reduction and automata evaluation for grammar-compressed trees
• “Syntactic” AC-unification
• One-context unification with STG-compressed terms is in NP
• First-order unification on compressed terms

This page was built for publication: Unification with Singleton Tree Grammars

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