ACUOS2: A High-Performance System for Modular ACU Generalization with Subtyping and Inheritance

María Alpuente; Demis Ballis; Angel Cuenca-Ortega; Santiago Escobar; José Meseguer

doi:10.1007/978-3-030-19570-0_11

ACUOS²: A High-Performance System for Modular ACU Generalization with Subtyping and Inheritance

María Alpuente, Demis Ballis, Angel Cuenca-Ortega, Santiago Escobar, José Meseguer

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Generalization in order-sorted theories with any combination of associativity (A), commutativity (C), and unity (U) algebraic axioms is finitary. However, existing tools for computing generalizers (also called “anti-unifiers”) of two typed structures in such theories do not currently scale to real size problems. This paper describes the ACUOS² system that achieves high performance when computing a complete and minimal set of least general generalizations in these theories. We discuss how it can be used to address artificial intelligence (AI) problems that are representable as order-sorted ACU generalization, e.g., generalization in lists, trees, (multi-)sets, and typical hierarchical/structural relations. Experimental results demonstrate that ACUOS² greatly outperforms the predecessor tool ACUOS by running up to five orders of magnitude faster.

Original language	English (US)
Title of host publication	Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Proceedings
Editors	Francesco Calimeri, Nicola Leone, Marco Manna
Publisher	Springer
Pages	171-181
Number of pages	11
ISBN (Print)	9783030195694
DOIs	https://doi.org/10.1007/978-3-030-19570-0_11
State	Published - 2019
Event	16th European Conference on Logics in Artificial Intelligence, JELIA 2019 - Rende, Italy Duration: May 7 2019 → May 11 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11468 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th European Conference on Logics in Artificial Intelligence, JELIA 2019
Country/Territory	Italy
City	Rende
Period	5/7/19 → 5/11/19

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1007/978-3-030-19570-0_11

Library availability

Discover UIUC Full Text

Cite this

Alpuente, M., Ballis, D., Cuenca-Ortega, A., Escobar, S., & Meseguer, J. (2019). ACUOS²: A High-Performance System for Modular ACU Generalization with Subtyping and Inheritance. In F. Calimeri, N. Leone, & M. Manna (Eds.), Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Proceedings (pp. 171-181). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11468 LNAI). Springer. https://doi.org/10.1007/978-3-030-19570-0_11

ACUOS² : A High-Performance System for Modular ACU Generalization with Subtyping and Inheritance. / Alpuente, María; Ballis, Demis; Cuenca-Ortega, Angel et al.

Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Proceedings. ed. / Francesco Calimeri; Nicola Leone; Marco Manna. Springer, 2019. p. 171-181 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11468 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Alpuente, M, Ballis, D, Cuenca-Ortega, A, Escobar, S & Meseguer, J 2019, ACUOS²: A High-Performance System for Modular ACU Generalization with Subtyping and Inheritance. in F Calimeri, N Leone & M Manna (eds), Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11468 LNAI, Springer, pp. 171-181, 16th European Conference on Logics in Artificial Intelligence, JELIA 2019, Rende, Italy, 5/7/19. https://doi.org/10.1007/978-3-030-19570-0_11

Alpuente M, Ballis D, Cuenca-Ortega A, Escobar S, Meseguer J. ACUOS²: A High-Performance System for Modular ACU Generalization with Subtyping and Inheritance. In Calimeri F, Leone N, Manna M, editors, Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Proceedings. Springer. 2019. p. 171-181. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-19570-0_11

Alpuente, María ; Ballis, Demis ; Cuenca-Ortega, Angel et al. / ACUOS² : A High-Performance System for Modular ACU Generalization with Subtyping and Inheritance. Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Proceedings. editor / Francesco Calimeri ; Nicola Leone ; Marco Manna. Springer, 2019. pp. 171-181 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4989df8474a64a9a9a812677a69d00e7,

title = "ACUOS2: A High-Performance System for Modular ACU Generalization with Subtyping and Inheritance",

abstract = "Generalization in order-sorted theories with any combination of associativity (A), commutativity (C), and unity (U) algebraic axioms is finitary. However, existing tools for computing generalizers (also called “anti-unifiers”) of two typed structures in such theories do not currently scale to real size problems. This paper describes the ACUOS2 system that achieves high performance when computing a complete and minimal set of least general generalizations in these theories. We discuss how it can be used to address artificial intelligence (AI) problems that are representable as order-sorted ACU generalization, e.g., generalization in lists, trees, (multi-)sets, and typical hierarchical/structural relations. Experimental results demonstrate that ACUOS2 greatly outperforms the predecessor tool ACUOS by running up to five orders of magnitude faster.",

author = "Mar{\'i}a Alpuente and Demis Ballis and Angel Cuenca-Ortega and Santiago Escobar and Jos{\'e} Meseguer",

note = "Funding Information: This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grant TIN 2015-69175-C4-1-R, by Generalitat Valenciana under grants PROM-ETEOII/2015/013 and PROMETEO/2019/098, and by NRL under contract number N00173-17-1-G002. Angel Cuenca-Ortega has been supported by the SENESCYT, Ecuador (scholarship program 2013). Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 16th European Conference on Logics in Artificial Intelligence, JELIA 2019 ; Conference date: 07-05-2019 Through 11-05-2019",

year = "2019",

doi = "10.1007/978-3-030-19570-0_11",

language = "English (US)",

isbn = "9783030195694",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "171--181",

editor = "Francesco Calimeri and Nicola Leone and Marco Manna",

booktitle = "Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Proceedings",

address = "Germany",

}

TY - GEN

T1 - ACUOS2

T2 - 16th European Conference on Logics in Artificial Intelligence, JELIA 2019

AU - Alpuente, María

AU - Ballis, Demis

AU - Cuenca-Ortega, Angel

AU - Escobar, Santiago

AU - Meseguer, José

N1 - Funding Information: This work has been partially supported by the EU (FEDER) and the Spanish MINECO under grant TIN 2015-69175-C4-1-R, by Generalitat Valenciana under grants PROM-ETEOII/2015/013 and PROMETEO/2019/098, and by NRL under contract number N00173-17-1-G002. Angel Cuenca-Ortega has been supported by the SENESCYT, Ecuador (scholarship program 2013). Publisher Copyright: © 2019, Springer Nature Switzerland AG.

PY - 2019

Y1 - 2019

N2 - Generalization in order-sorted theories with any combination of associativity (A), commutativity (C), and unity (U) algebraic axioms is finitary. However, existing tools for computing generalizers (also called “anti-unifiers”) of two typed structures in such theories do not currently scale to real size problems. This paper describes the ACUOS2 system that achieves high performance when computing a complete and minimal set of least general generalizations in these theories. We discuss how it can be used to address artificial intelligence (AI) problems that are representable as order-sorted ACU generalization, e.g., generalization in lists, trees, (multi-)sets, and typical hierarchical/structural relations. Experimental results demonstrate that ACUOS2 greatly outperforms the predecessor tool ACUOS by running up to five orders of magnitude faster.

AB - Generalization in order-sorted theories with any combination of associativity (A), commutativity (C), and unity (U) algebraic axioms is finitary. However, existing tools for computing generalizers (also called “anti-unifiers”) of two typed structures in such theories do not currently scale to real size problems. This paper describes the ACUOS2 system that achieves high performance when computing a complete and minimal set of least general generalizations in these theories. We discuss how it can be used to address artificial intelligence (AI) problems that are representable as order-sorted ACU generalization, e.g., generalization in lists, trees, (multi-)sets, and typical hierarchical/structural relations. Experimental results demonstrate that ACUOS2 greatly outperforms the predecessor tool ACUOS by running up to five orders of magnitude faster.

UR - http://www.scopus.com/inward/record.url?scp=85065977923&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065977923&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-19570-0_11

DO - 10.1007/978-3-030-19570-0_11

M3 - Conference contribution

AN - SCOPUS:85065977923

SN - 9783030195694

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 171

EP - 181

BT - Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Proceedings

A2 - Calimeri, Francesco

A2 - Leone, Nicola

A2 - Manna, Marco

PB - Springer

Y2 - 7 May 2019 through 11 May 2019

ER -