Context Unification is in PSPACE

DOI10.1007/978-3-662-43951-7_21zbMath1409.68150arXiv1310.4367OpenAlexW1492050056MaRDI QIDQ5167842

Artur Jeż

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.4367

zbMATH Keywords

term rewritingsecond-order unificationcontext unification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Related Items (8)

Approximation of smallest linear tree grammar ⋮ Regular matching and inclusion on compressed tree patterns with constrained context variables ⋮ Unnamed Item ⋮ Grammar-based compression of unranked trees ⋮ Unnamed Item ⋮ Inter-procedural Two-Variable Herbrand Equalities ⋮ The hardness of solving simple word equations ⋮ One-variable word equations in linear time

This page was built for publication: Context Unification is in PSPACE