One-context unification with STG-compressed terms is in NP

DOI10.4230/LIPICS.RTA.2012.149MaRDI QIDQ5111902zbMATHOpenAlexFDO

Authors Carles Creus, Adrià Gascón, Guillem Godoy

Publication date 27 May 2020

Full work available at URL https://dblp.uni-trier.de/db/conf/rta/rta2012.html#CreusGG12

zbMATH Keywords

compressiongrammarsterm unification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Recommendations

• Unification and matching on compressed terms
• Unification with Singleton Tree Grammars
• First-order unification on compressed terms
• Deciding context unification
• Two-restricted one context unification is in polynomial time

Cited in

(7)

• One context unification problems solvable in polynomial time
• First-order unification on compressed terms
• Approximation of smallest linear tree grammar
• Grammar-Based Tree Compression
• Unification with Singleton Tree Grammars
• Stratified Context Unification Is NP-Complete
• Two-restricted one context unification is in polynomial time

This page was built for publication: One-context unification with STG-compressed terms is in NP

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