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

DOI10.4230/LIPICS.RTA.2012.149zbMATH Open1437.68078OpenAlexW1836750303MaRDI QIDQ5111902FDOQ5111902

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

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

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)

Cited In (7)

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

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)