Description Logic with part restrictions: PSPACE-complete expressiveness

dc.contributor.author	Yanchev, Mitko
dc.date.accessioned	2015-07-21T07:56:18Z
dc.date.available	2015-07-21T07:56:18Z
dc.date.issued	2014
dc.identifier.uri	http://hdl.handle.net/10506/1357
dc.description	Presented at CiE2014 as contributed talk.	bg
dc.description.abstract	In this paper syntactic objects-concept constructors, called part restrictions-are considered in Description Logics (DLs). Being able to convey statements about a part of a set of successors, part restrictions essentially enrich the expressive capabilities of DLs. An extension of DL ALCQR with part restrictions is examined, and its PSPACE completeness is proven, what shows that the new expressiveness brings no extra cost to the complexity of reasoning in ALCQR. The proof uses completion calculus based on tableaux technique.	bg
dc.description.sponsorship	This work was supported by the European Social Fund through the Human Resource Development Operational Programme under contract BG051PO001-3.3.06-0052 (2012/2014).	bg
dc.language.iso	en	bg
dc.relation.ispartofseries	CiE2014;June 25, 2014
dc.subject	Description Logics	bg
dc.subject	part restrictions	bg
dc.subject	complexity	bg
dc.subject	PSPACE	bg
dc.title	Description Logic with part restrictions: PSPACE-complete expressiveness	bg
dc.type	Other	bg