A correct, precise and efficient integration of set-sharing, freeness and linearity for the analysis of finite and rational tree languages Export

@misc{citeulike:296729, abstract = {It is well-known that freeness and linearity information positively interact with aliasing information, allowing both the precision and the efficiency of the sharing analysis of logic programs to be improved. In this paper we present a novel combination of set-sharing with freeness and linearity information, which is characterized by an improved abstract unification operator. We provide a new abstraction function and prove the correctness of the analysis for both the finite tree and the rational tree cases. Moreover, we show that the same notion of redundant information as identified in (Bagnara et al. 2002; Zaffanella et al. 2002) also applies to this abstract domain combination: this allows for the implementation of an abstract unification operator running in polynomial time and achieving the same precision on all the considered observable properties.}, archivePrefix = {arXiv}, author = {Hill, Patricia M. and Zaffanella, Enea and Bagnara, Roberto}, citeulike-article-id = {296729}, citeulike-linkout-0 = {http://arxiv.org/abs/cs.PL/0401021}, citeulike-linkout-1 = {http://arxiv.org/pdf/cs.PL/0401021}, day = {26}, eprint = {cs.PL/0401021}, keywords = {analysis, linearity, logic, programming, theory, tree}, month = {Jan}, posted-at = {2005-08-17 18:18:11}, priority = {2}, title = {A correct, precise and efficient integration of set-sharing, freeness and linearity for the analysis of finite and rational tree languages}, url = {http://arxiv.org/abs/cs.PL/0401021}, year = {2004} }

TY - ELEC ID - citeulike:296729 L3 - citeulike-article-id:296729 N2 - It is well-known that freeness and linearity information positively interact with aliasing information, allowing both the precision and the efficiency of the sharing analysis of logic programs to be improved. In this paper we present a novel combination of set-sharing with freeness and linearity information, which is characterized by an improved abstract unification operator. We provide a new abstraction function and prove the correctness of the analysis for both the finite tree and the rational tree cases. Moreover, we show that the same notion of redundant information as identified in (Bagnara et al. 2002; Zaffanella et al. 2002) also applies to this abstract domain combination: this allows for the implementation of an abstract unification operator running in polynomial time and achieving the same precision on all the considered observable properties. TI - A correct, precise and efficient integration of set-sharing, freeness and linearity for the analysis of finite and rational tree languages KW - analysis KW - linearity KW - logic KW - programming KW - theory KW - tree AU - Hill, Patricia AU - Zaffanella, Enea AU - Bagnara, Roberto PY - 2004/Jan/26/ UR - http://arxiv.org/abs/cs.PL/0401021 ER -