Decidability

First-order logic is semi-decidable for satisfiability and entailment. For problems requiring the full expressiveness of first-order logic we have to live with this shortcoming, and - as experience shows - can often do so without negative consequences. Many practically occurring problems, however, are sufficiently constrained so that they can be expressed and solved in a decidable subset of first-order logic. Other problems, for instance those arising in safety-critical domains, even absolutely require decidability.

Of the many decidable subsets of first-order logic that have been identified so far, description logics and languages derived from description logics, for instance OWL DL, seem to be the most relevant in the context of REWERSE.

As the case of propositional logic shows, decidability does not necessarily imply computa-tional tractability. Thus tractability is a separate issue. While OWL DL and its subset OWL Lite have been carefully designed to be tractable, their superset OWL Full comes without any computational guarantees.

Attempto Controlled English (ACE) – designed to provide high expressiveness – is equivalent to full first-order logic and thus semi-decidable. The question we plan to investigate is ’Which decidable, tractable and sufficiently expressive subsets does ACE have?’. Furthermore, these subsets must be clearly defined to be acceptable to the users of ACE.

Here are two approaches to find decidable, tractable and sufficiently expressive subsets of ACE.

In the first approach we restrict the syntax of ACE and then investigate the properties of the resulting sublanguage. A similar approach was chosen by Pratt-Hartmann [7] who de-fined a series of fragments of English and then for each fragment identified the computational complexity of determining satisfiability and entailment. Pratt-Hartmann’s results are not very encouraging since his more expressive fragments of English have either exponential complexity or are undecidable.

The basic idea of the second approach is to map a suitable decidable and tractable subset of first-order logic, for instance OWL DL, to a subset of ACE. Before we can do this, however, we need to extend ACE at least by language constructs to describe classes and operations on classes. The mapping from first-order logic constructs to ACE constructs has to be done manually but could by supported by the Attempto verbalisation component (cf. “Verbalisation of Formal Languages” above).

Bibliography

[1] http://www.ics.mq.edu.au/ rolfs/controlled-natural-languages (controlled natural language homepage), 2004.

[2] G. Antoniou, M. J. Maher, and D. Billington. Defeasible logic versus logic programming without negation as failure. Journal of Logic Programming, 42(1):47–57, 2000.

[3] M. Gelfond and V. Lifschitz. Logic programs with classical negation. In Proc. of Int. Conf.

on Logic Programming. MIT Press, 1990.

[4] M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive databases.

New Generation Computing, 9:365–385, 1991.

[5] B. Grosof. Prioritized conflict handling for logic programs. In Proc. International Symposium on Logic Programming (ILPS-97), 1997.

[6] D. Pearce and G. Wagner. Reasoning with negative information I – strong negation in logic programs. In M. K. L. Haaparanta and I. Niiniluoto, editors, Language, Knowledge and Intentionality. Acta Philosophica Fennica 49, 1990.

[7] I. Pratt-Hartmann. Fragments of language. Journal of Logic, Language and Information, (13):207–223, 2004.

[8] G. Wagner. A database needs two kinds of negation. In B. Thalheim and H.-D. Gerhardt, editors, Proc. of the 3rd. Symp. on Mathematical Fundamentals of Database and Knowledge Base Systems, volume 495 of Lecture Notes in Computer Science, pages 357–371. Springer-Verlag, 1991.

[9] T. Y. C. Woo and S. S. Lam. Authorizations in distributed systems: A new approach.

Journal of Computer Security, 2(2-3):107–136, 1993.

Part II

Requirements and Scenarios

Chapter 6

Reference scenarios

6.1 A European use case on financial services

Background: This use case for European financial services was originally presented by Steve Ross-Talbot; it involves Basel 2 [1], which is a major initiative in Europe to enforce policy within the financial services domain. This includes retail and wholesale banking as well as insurance services. The aim of Basel 2 is to ensure that the capital adequacy is properly enforced across all financial service transactions within Europe. This includes everything from pensions to insurance and mortgages.

As we move to a Europe which is free of barriers to trade we shall see more and more cross border selling of financial service products. These products and services range from mortgages to insurance to general savings products. These products underpin the fabric of European life from secure accommodation for European citizens, to pensions. Further, it secures real inward investment in European industry through equity participation and through European wide fixed income products.

In Europe today it is not made easy for consumers to purchase such products nor is it made easy for consumers to manage those products through their life cycle. Initiatives in member states are trying to address some of the issues as they pertain to the entire life cycle of financial service products (e.g. Britain’s FSA’s¹CP98 [2], CP121 [3], CP136 [4]). In Europe many of the same issues are being addressed by Basel 2. The result will be a regulated and safe environment in which products can be bought and sold and in which a fair market can be ensured through the semantic comparisons necessary to support fair trade.

It is against this landscape and these regulatory requirements that we set out the use case to show the relevance of rules and the power of the Semantic Web in meeting the needs of European citizens and empowering them through the web to continue to purchase and manage European financial service products.

Scenario: Our scenario involves buying a simple mortgage package that includes some level of insurance that is used to underpin the risks inherent in products that have a very long lifetime, while leveraging a rules-based Semantic Web.

Juan Sebastien is moving from Madrid, having got a new job in Kaiserslautern. He would like to buy an apartment in Kaiserslautern for him and his family. He is married with one

1http://www.fsa.gov.uk/

child and his wife is expecting their second in about 6 months. Before he leaves he wants to buy a mortgage package (mortgage, property insurance and life insurance) that suits his needs.

Being a citizen of Europe he would like to buy from Europe and is seeking the best solution.

Today he can barely identify the best solution, since there is no way for him to easily compare products which have a varied set of add-ons or give-back clauses attached to them, or even be aware and understand them.

The Semantic Web of the future will provide Juan Sebastien with the necessary self-support to buy the products that he wants over the web. It will provide him with the ability to compare products through the use of rule based agents and ontologies, the underpinning of the Semantic Web. Juan Sebastien, in this brave new world, will be able to ask questions of the Semantic Web that he has never been able to ask of the web before, such as,

• What is the cheapest product?

• Why do I need to provide a 20% deposit for this product?

• Why does Bank X deny my request for product Y?

• If I am locally employed, but without citizenship, yet living more than 3 years there, can I still get the special discount “as advertised”?

Furthermore, the back-office functions can be guaranteed to ensure that policy, as it pertains to Basel 2 is adhered to, and that Juan Sebastien’s rights, as they pertain to freedom of information (why not as well as why), are maintained.

Another typical complication is if Juan’s company is an international company, with global rules for employee’s eligibilities, and with added local variation as necessary.

We propose Rule-Based Semantic Web technology to provide a higher level of self-support in such scenarios: Rule-Based Semantic Web technology is a precursor – its ontological mod-eling being of paramount importance to the ability to compare concepts – to the reasoning, compliance as well as positive and negative explanations for decisions that are made. The rules will ensure the consistency of the policy, easy sharing (even across national boundaries), and of course, easy update.

Novelty of the approach

• European Business Language

– Rules are in the common business language of the provider – Questions/explanation are in the language of the consumer

– Markup techniques (based on an XML language like RuleML) for rule exchange between providers and between agents on the web

• User Empowerment

– Domain specific templates and natural language techniques to ensure user’s inde-pendence in rules maintenance

– Knowledge sharing, rules visibility and easy exchange of ideas as part of the Semantic Web

• Advanced queries and reasoning

– Why and why not queries – What-if queries

• Enhanced Productivity

– A single specification for business rules enforcement and advanced queries