Web Reasoning and Rule Systems

Homogeneous unstructured data (HUD) are collections of unstructured documents that share common properties, such as similar layout, common file format, or common domain of values. Building on such properties, it would be desirable to automatically process HUD to access the main information through a semantic layer – typically an ontology – called semantic view. Hence, we propose an ontology-based approach for extracting semantically rich information from HUD, by integrating and extending recent technologies and results from the fields of classical information extraction, table recognition, ontologies, text annotation, and logic programming. Moreover, we design and implement a system, named KnowRex, that has been successfully applied to curriculum vitae in the Europass style to offer a semantic view of them, and be able, for example, to select those which exhibit required skills.

Answer Set Programming (ASP) is logic programming under the stable model or answer set semantics. During the last decade, this paradigm has seen several extensions by generalizing the notion of atom used in these programs. Among these, there are dl-atoms, aggregate atoms, HEX atoms, generalized quantifiers, and abstract constraints. In this paper we refer to these constructs collectively as generalized atoms. The idea common to all of these constructs is that their satisfaction depends on the truth values of a set of (non-generalized) atoms, rather than the truth value of a single (non-generalized) atom. Motivated by several examples, we argue that for some of the more intricate generalized atoms, the previously suggested semantics provide unintuitive results and provide an alternative semantics, which we call supportedly stable or SFLP answer sets. We show that it is equivalent to the major previously proposed semantics for programs with convex generalized atoms, and that it in general admits more intended models than other semantics in the presence of non-convex generalized atoms. We show that the complexity of supportedly stable answer sets is on the second level of the polynomial hierarchy, similar to previous proposals and to answer sets of disjunctive logic programs.

Heuristic search is arguably the most successful paradigm in Automated Planning, which greatly improves the performance of planning strategies. However, adding heuristics usually leads to very complicated planning algorithms. In order to study different properties (e.g. completeness) of those complicated planning algorithms, it is important to use an appropriate formal language and framework. In this paper, we argue that Transaction Logic is just such a specification language, which lets one formally specify both the heuristics, the planning algorithm, and also facilitates the discovery of more general and more efficient algorithms. To illustrate, we take the well-known regression analysis mechanism and show that Transaction Logic lets one specify the concept of regression analysis easily and thus express \(\textit{RSTRIPS}\), a classical and very complicated planning algorithm based on regression analysis. Moreover, we show that extensions to that algorithm that allow indirect effects and action ramification are obtained almost for free. Finally, a compact and clear logical formulation of the algorithm lets us prove the completeness of \(\textit{RSTRIPS}\)—a result that, to the best of our knowledge, has not been known before.

In this paper we use results from Computable Set Theory as a means to represent and reason about description logics and rule languages for the semantic web.

Specifically, we introduce the description logic \(\mathcal {DL}\langle 4LQS^R\rangle (\mathbf {D})\)–allowing features such as min/max cardinality constructs on the left-hand/right-hand side of inclusion axioms, role chain axioms, and datatypes–which turn out to be quite expressive if compared with \(\mathcal {SROIQ}(\mathbf {D})\), the description logic underpinning the Web Ontology Language OWL. Then we show that the consistency problem for \(\mathcal {DL}\langle 4LQS^R\rangle (\mathbf {D})\)-knowledge bases is decidable by reducing it, through a suitable translation process, to the satisfiability problem of the stratified fragment \(4LQS^R\) of set theory, involving variables of four sorts and a restricted form of quantification. We prove also that, under suitable not very restrictive constraints, the consistency problem for \(\mathcal {DL}\langle 4LQS^R\rangle (\mathbf {D})\)-knowledge bases is NP-complete. Finally, we provide a \(4LQS^R\)-translation of rules belonging to the Semantic Web Rule Language (SWRL).

In the travel industry it is common for tour operators to pre-book from service suppliers blocks of package tours, which are called allotments in jargon. The selection of package tours is done according to several preference criteria aimed at maximizing the expected earnings given a budget. In this paper we formalize an allotment problem that abstracts the requirements of a real travel agent, and we solve it using Answer Set Programming. The obtained specification is executable, and it implements an advanced feature of the iTravel+ system.

Reasoning engines for ontological and rule-based knowledge bases are becoming increasingly important in areas like the Semantic Web or information integration. It has been acknowledged however that judging the performance of such reasoners and their underlying algorithms is difficult due to the lack of publicly available datasets with large amounts of (real-life) instance data. In this paper we describe a framework and a toolbox for creating such datasets, which is based on extracting instances from the publicly available OpenStreetMap (OSM) geospatial database. To this end, we give a formalization of OSM and present a rule-based language to specify the rules to extract instance data from OSM data. The declarative nature of the approach in combination with external functions and parameters allows one to create several variants of the dataset via small modifications of the specification. We describe a highly flexible toolbox to extract instance data from a given OSM map and a given set of rules. We have employed our tools to create benchmarks that have already been fruitfully used in practice.

Advances in the Internet of Things and the Web of Data created huge opportunities for developing applications that can generate actionable knowledge out of streaming data. The trade-off between scalability and expressivity is a key challenge in this setting, and more investigation is required to identify what are the relevant features in optimizing this trade-off, and what role do they have in the optimization. In this paper we motivate the need for heuristics to design adaptive solutions and, following an empirical approach, we highlight some key concepts and ideas that can guide the design of heuristics for adaptive optimization of Web Stream Reasoning.

Event-Condition-Action languages are the commonly accepted paradigm to express and model the behavior of reactive systems. While numerous Event-Condition-Action languages have been proposed in the literature, differing e.g. on the expressivity of the language and on its operational behavior, existing Event-Condition-Action languages do not generally support the action component to be formulated as a transaction. In this paper, sustaining that it is important to execute transactions in reactive languages, we propose an Event-Condition-Transaction language, based on an extension of Transaction Logic. This extension, called Transaction Logic with Events (\(\mathcal {TR}^{ev}\)), combines reasoning about the execution of transactions with the ability to detect complex events. An important characteristic of \(\mathcal {TR}^{ev}\) is that it takes a choice function as a parameter of the theory, leaving open the behavioral decisions of the logic, and thereby allowing it to be suitable for a wide-spectrum of application scenarios like Semantic Web, multi-agent systems, databases, etc. We start by showing how \(\mathcal {TR}^{ev}\) can be used as an Event-Condition-Action language where actions are considered as transactions, and how to differently instantiate this choice function to achieve different operational behaviors. Then, based on a particular operational instantiation of the logic, we present a procedure that is sound and complete w.r.t. the semantics and that is able to execute \(\mathcal {TR}^{ev}\) programs.