TY - CHAP
T1 - Initial Steps Towards a Family of Regular-Like Plan Description Logics
AU - Borgida, Alexander
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - A wide range of ordinary Description Logics (DLs) have been explored by considering collections of concept/role constructors, and types of terminologies, yielding an array of complexity results. Representation and reasoning with plans is a very important topic in AI, yet there has been very little work on finding and studying DL constructors for plan concepts. We start to remedy this problem here by considering Plan DLs where concept instances are sequences of action instances, and hence plan concepts can be viewed as analogues of formal languages, describing sets of strings. Inspired by the clasp system, we consider using regular-like expressions, obtaining a rich variety of Plan DLs based on combinations of regular-like expression constructors, including sequence (concatenation), alternation (union, disjunction), looping (Kleene star), conjunction (intersection), and complement. To model the important notion of concurrency, we also consider interleaving. We present results from the formal language literature which have immediate bearing on the complexity of DL-like reasoning tasks. However, we also focus on succinctness of representation, and on expressive power, issues first studied by Franz Baader for ordinary DLs.
AB - A wide range of ordinary Description Logics (DLs) have been explored by considering collections of concept/role constructors, and types of terminologies, yielding an array of complexity results. Representation and reasoning with plans is a very important topic in AI, yet there has been very little work on finding and studying DL constructors for plan concepts. We start to remedy this problem here by considering Plan DLs where concept instances are sequences of action instances, and hence plan concepts can be viewed as analogues of formal languages, describing sets of strings. Inspired by the clasp system, we consider using regular-like expressions, obtaining a rich variety of Plan DLs based on combinations of regular-like expression constructors, including sequence (concatenation), alternation (union, disjunction), looping (Kleene star), conjunction (intersection), and complement. To model the important notion of concurrency, we also consider interleaving. We present results from the formal language literature which have immediate bearing on the complexity of DL-like reasoning tasks. However, we also focus on succinctness of representation, and on expressive power, issues first studied by Franz Baader for ordinary DLs.
UR - http://www.scopus.com/inward/record.url?scp=85068423693&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85068423693&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-22102-7_4
DO - 10.1007/978-3-030-22102-7_4
M3 - Chapter
AN - SCOPUS:85068423693
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 90
EP - 109
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PB - Springer Verlag
ER -