Abstract
We extend first-order order-sorted unification by permitting regular expression sorts for variables and in the domains of function symbols. The set of basic sorts is finite. The obtained signature corresponds to a finite bottom-up hedge automaton. The unification problem in such a theory generalizes some known unification problems. Its unification type is infinitary. We give a complete unification procedure and prove decidability.
BibTeX - Entry
@InProceedings{kutsia_et_al:LIPIcs:2010:2653,
author = {Temur Kutsia and Mircea Marin},
title = {{Order-Sorted Unification with Regular Expression Sorts}},
booktitle = {Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
pages = {193--208},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-18-7},
ISSN = {1868-8969},
year = {2010},
volume = {6},
editor = {Christopher Lynch},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2653},
URN = {urn:nbn:de:0030-drops-26537},
doi = {10.4230/LIPIcs.RTA.2010.193},
annote = {Keywords: Unification, sorts, regular expression}
}
|
Keywords: |
|
Unification, sorts, regular expression |
|
Collection: |
|
Proceedings of the 21st International Conference on Rewriting Techniques and Applications |
|
Issue Date: |
|
2010 |
|
Date of publication: |
|
06.07.2010 |
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)