Model-Theoretic Semantics for the Web


James Farrugia

National Center for Geographic Information and Analysis
Department of Spatial Information Science and Engineering, University of Maine
Orono, Maine 04469-5711 USA
1 207 866 6523

jim@spatial.maine.edu

 

 Copyright is held by the author/owner(s).
WWW2003, May 20-24, 2003, Budapest, Hungary.
ACM 1-58113-680-3/03/0005.


ABSTRACT

Model-theoretic semantics is a formal account of the interpretations of legitimate expressions of a language. It is increasingly being used to provide Web markup languages with well-defined semantics. But a discussion of its roles and limitations for the Semantic Web has not yet received a coherent and detailed treatment. This paper takes the first steps towards such a treatment. The major result is an introductory explication of key ideas that are usually only implicit in existing accounts of semantics for the Web. References to more detailed accounts of these ideas are also provided. The benefit of this explication is increased awareness among Web users of some important issues inherent in using model-theoretic semantics for Web markup languages.

Categories and Subject Descriptors

F.4.4 [Mathematical Logic and Formal Languages]: Mathematical Logic - Model theory

General Terms

Languages, Standardization, Theory

Keywords

Model-theoretic semantics, Web markup languages, semantics

 

Copyright is held by the author/owner(s).

WWW 2003, May 20-24, 2003, Budapest, Hungary.

ACM 1-58113-680-3/03/0005.

 

1.     INTRODUCTION

Model-theoretic semantics is an "account of meaning in which sentences are interpreted in terms of a model of, or abstract formal structure representing, an actual or possible state of the world" [6]. Such an account of meaning, deeply rooted in logic, is being used to provide certain Web markup languages with formal semantic foundations [14, 35]. It is expected that software programs will build on these foundations to enable computers to carry out limited forms of automated reasoning across the Web [3]. Yet, there is little material available for prospective users of these languages that puts into context the basic issues concerning the use of model-theoretic semantics on the Web.

There do exist, of course, explanations and tutorials that address certain theoretical or practical aspects of a given Web markup language like DAML+OIL [23, 34], as well as works in progress that introduce the new Web Ontology Language OWL [30, 35].

One also finds popular accounts of semantics on the Web that attempt to strike a balance between sketching a vision of the Semantic Web and providing just enough details of logic to make that vision plausible [2, 3]. But in the former case, the explanations are typically directed at rather narrow audiences and so often omit discussion of semantic issues relevant to a broader group of prospective users and developers. In the latter case, although the accounts do succeed in suggesting some capabilities of a future Semantic Web, they do not make sufficiently clear how these capabilities are related to logic.

Thus, in neither type of treatment can we find extended discussions of the strengths and weaknesses of the model-theoretic approach to semantics for the Web (which are also generally shared by any formal account of meaning). Such discussions would be highly valuable to managers, developers, and users, all of whom can benefit by understanding what this approach can and cannot do for them. This paper takes the first step toward filling a gap in the literature on the use of formal semantics for the Web. Its aim is to balance a broad-based discussion with just enough detail to give readers a suitable background for understanding other, more in-depth accounts of model-theoretic semantics, some of which can be found in the references. The focus here is on certain key definitional and philosophical fundamentals; left for future work is the much-needed discussion of implementation issues. The goal of this paper is to convince readers that the topics dealt with here deserve a fuller, more coherent treatment than they have so far received from the Semantic Web community.

We assume the reader has some familiarity with RDF [27] and the RDF Schema work in progress [5], together referred to here as RDF/S. We attempt to explain basic model-theoretic ideas without burdening the reader with the heavy doses of syntax found in those documents. It may also be useful if the reader has close at hand the draft of RDF Semantics [14], referred to here as RDFMT (for RDF Model Theory). Although the latest Web markup languages do have more features than RDF/S, this paper does not attempt to explain the intricacies of these languages, and the examples we use can be understood by someone who is not familiar with the details of those languages. Another reason to hew closely to RDF/S is that although there is not much centralized discussion of the role of model-theoretic semantics for the Web, much of the consolidated material that currently does exist can be found in RDFMT.

The remainder of this paper is structured as follows. Section 2 explains what a model-theoretic semantics provides, how it provides what it does, and what its uses and limitations are. A major theme in this section is the inherent tension between the use of what might be termed "human-meaningful" semantics for the Web and the use of formal, model-theoretic semantics. Section 3 discusses certain terminological hurdles (e.g., the very use of the term 'model') that can easily impede a reader's understanding of the subject. Section 4 puts model-theoretic semantics into a broader context by relating it to several relevant philosophical issues, an adequate discussion of which would require more space than is available here. Section 5 gives a summary and conclusion.

2.     MODEL-THEORETIC SEMANTICS

A major aspiration of proponents of the Semantic Web is to have machines be able to "reason about Web content, and produce an intelligent result to unforeseen situations." [26]. Fundamental to understanding how well this aspiration might be met is a firm grasp of the basic roles and limitations of formal semantics for the Web. To this end, we discuss in Section 2.1 what model-theoretic semantics does and does not do, and in Section 2.2 we explain how it accomplishes what it does.

Note that, particularly in discussions of semantics for the Web, not everyone understands the word 'semantics' in the same way. Broadly speaking, one can discern in these discussions two main views on what semantics is and how it can be exploited for the Web. In one view, the semantics of information resources deals with the human-perceived meanings associated with those resources. According to this view, if a document carries metadata tags, such as '<AUTHOR>' or '<TITLE>' in some XML-based language, the meanings conveyed by these tags are simply those meanings that happen to work for their creators and users. In the other view, 'semantics' is generally taken to mean model-theoretic semantics, which uses abstract structures (see Section 2.2.1) to assign interpretations to legitimate language constructs. When the developers of recent Web markup languages discuss semantic issues, they typically do so with this latter meaning in mind. In Section 2.3 we discuss both these views of semantics and the difficulties inherent in keeping each of them in its proper place.

2.1     What it does and does not do

As the definition in the Introduction suggests, the model-theoretic approach to semantics accounts for meanings via some sort of formal structure. In a certain sense, this structure comes between sentences of a language and the resources that these sentences describe.

At first glance it seems odd that we should use some sort of intervening abstract structure to account for meanings. Why can't we simply take the statements of a given language to be directly about the information resources and properties that they describe?

For instance, why can't we understand the RDF triple <Jane Smith, mother_of, John Smith> as referring directly to Jane Smith, John Smith, and the relationship of 'is_the_mother_of', in this way accounting for the meaning of 'Jane Smith is the mother of John Smith' directly, without having to introduce some sort of intervening abstract structure? 

We can, but by so doing we limit our ability to use machines to do the following four tasks:

1.        interpret unambiguously the legitimate expressions of a given language;

2.        evaluate the truth of a language statement under a particular interpretation;

3.        carry out automated reasoning with these statements (e.g., "Statement C is entailed by statements A and B.");

4.        incorporate statements made available elsewhere on the Web into our own set of statements, automatically and insofar as possible without contradiction.

These tasks are important to the future of the Semantic Web, because people will come to expect machines to be able to do all of these tasks, as for example when we invoke software agents to search for, reason about, and execute Web services on our behalf. Model-theoretic semantics, along with related language techniques being developed for Web markup languages, can allow us to accomplish these tasks. (The actual implementation of these tasks depends on an appropriate, implementable proof theory used in conjunction with the model theory.)

By introducing an intervening abstract structure to interpret language statements, the model-theoretic approach allows us to accomplish the first two tasks, because

·           interpretations of legitimate language expressions are given in terms of the abstract structure;

·           the truth of a statement is evaluated as a claim about the abstract structure;

·           the relevant parts of this structure can be encoded into and processed by a machine (e.g., [4]); and

·           the truth of a statement under a given interpretation can then be assessed mechanically.

Using model-theoretic semantics, we can also accomplish the third task, because

·           the notion of entailment lies at the heart of logical reasoning (automated or not), and

·           entailment is defined in terms of interpretations [20], which as formal structures can give rise to algorithms for reasoning.

(Interpretations can be thought of as possible states of affairs, and entailment can be seen as the license to conclude the truth of one statement from the truth of another, whatever the legitimate possible states of affairs might be. Interpretations and entailment are discussed in more depth in Sections 2.2.1 and 2.2.2, respectively.)

Additional techniques, such as the handling of statements imported from various Web sources, should also allow us to accomplish the fourth task. However, techniques that allow the importing of and reasoning with statements from diverse sources are still under active development. (See, for example, discussions among members of the W3C's Web Ontology Working Group for November, 2002 at http://lists.w3.org/Archives/Public/www-webont-wg/2003Feb/.) A discussion of the semantics of imported statements is beyond the scope of this paper.

Although the model-theoretic approach is an accepted paradigm for providing a formal account of meaning and entailment, there are some important things it cannot do. We discuss two of them.

1)       Model-theoretic semantics does not pretend, and has no way to determine what certain words and statements "really" mean.

a)        It does not permit machines to understand meanings in the ways that humans understand natural language. In fact, developers of the latest Web markup languages are deliberately steering away from natural-language semantics. According to RDFMT, "[t]he chief utility of a formal semantic theory is not to provide any deep analysis of the nature of the things being described by the language ... but to provide a technical way to determine when inference processes are valid" [14].

b)       In a discussion of the interpretation of sentences in first-order logic, Hodges says, "first-order sentences were never intended to mean anything; rather they were designed to express conditions which things can satisfy or fail to satisfy" [20, emphasis in original].

c)        Etchemendy and Barwise say, "After all, specifying which sentences or uses of sentences are in fact true is not part of the semanticist's business; if it were, the task would obviously be hopeless." ... [The issue is] "not whether it is in fact true but rather under what conditions it can be used to make a true claim" [11, emphasis in original].

d)       Hodges also says, "One also talks of model-theoretic semantics of natural languages, which is a way of describing the meanings of natural language sentences, not a way of giving them meanings" [19, emphasis in original].

2)       It offers no help in making the connection between the model (the abstract structure) and the world.

a)        Consider, for example, all the different ways humans might interpret the  'is_the_mother_of' relation (legally, biologically, socially, metaphorically, ...). Model-theoretic semantics provides no guidance to help us agree which of these real-world senses of 'is_the_mother_of' is the one we want to use.

b)       "Model theory is not a semantical theory which relates natural languages to the physical and social reality, but rather a mathematical theory which relates some mathematical structures to other mathematical structures." [32].

c)        It offers no particularly easy interface for people to understand how it handles meanings [35]. It can be argued, though, that what it loses in this regard it makes up for by its precision.

In a nutshell, then, what model-theoretic semantics does is: 1) use formal structures and rules to ensure that every legitimate language expression has a well-defined meaning; 2) define what is means for a statement in a language to be true under a particular interpretation; 3) allow us to formalize the intuitive notion of logical consequence, that is, of one statement 'following logically' from others; and 4) provide a basis for implementing automated reasoning via an appropriate proof theory. What model-theoretic semantics does not do is give meanings to natural-language expressions or help us mediate between the abstractions it uses and the real world.

Thus, if there is a special magic to the model-theoretic approach, it does not have to do with the "real" meanings of language expressions or with any connection between these expressions and the everyday world. Rather, whatever magic this approach may have appears to lie in its ability to provide a formal framework that can consolidate agreements on how interpretations are made and truth values are assigned, as well as specify when we are warranted in making inferences. This formal approach provides "a rigorous definition to a notion of 'meaning' that can be related directly to computable methods of determining whether or not meaning is preserved by some transformation on a representation of knowledge" [14].

2.2     How it does it

A model-theoretic semantics for a given language allows us to:

1.        assign well-defined interpretations to legitimate expressions in a language;

2.        interpret statements in the language;

3.        assess the truth value of these statements under a given interpretation; and

4.        define what it means for one statement to 'follow logically' from other statements.

It accomplishes these tasks by specifying how to construct interpretations and how to define entailment.

2.2.1     Interpretations

Consider the statement 'Jane is the mother of John'. We can think of its model-theoretic interpretation as being carried out in two steps:

1.        the components of this statement are interpreted in terms of an abstract structure (a set with particular functions and relations defined on it, along with certain elements distinguished in it [21]); and

2.        the whole statement is interpreted by evaluating whether the claim it makes about the abstract structure, according to the interpretations in step 1, is true or false.

(In some accounts of model-theoretic semantics, a distinction is made between the interpretation of a statement in a structure and the assignment of a truth value to this statement. In RDFMT, however, the interpretation of a statement (i.e., of an RDF triple) is a truth value [14]. We adopt this convention in this paper, thus collapsing the distinction made by separating points 2 and 3 above .)

For example, we can think of the model-theoretic interpretation of 'Jane is the mother of John' being carried out as follows. First, given some set (sometimes called the "universe"), we interpret 'Jane' as an element of this set, 'John' as an element of this set, and 'is_the_mother_of' as a relation on this set. Second, we consider the whole statement 'Jane is the mother of John' to be, once its components have been interpreted, a claim about the state of affairs in the structure. The claim being made is the following: in the 'is_the_mother_of' relation on the universe, there is an ordered pair whose first element is the interpretation of 'Jane' and whose second element is the interpretation of 'John'. If this claim holds true in the structure, one says that 'Jane is the mother of John' is true in the structure, or true in the structure under the given interpretation. (Note that in the semantics for RDF/S, the interpretation of relations is done in a rather more complex way [14].)

In general, when the interpretation of a statement is true in a structure one says that the statement is satisfied in this structure. In such a case, following practice in mathematical logic, the structure is called a model of the statement [36]; hence, the term 'model' in 'model-theoretic semantics.'

It can be useful to distinguish between structures and interpretations of language elements, because structures can exist and be treated without reference to the interpretation of the elements of a particular language [29]. But a structure can also be intimately tied to a given language by rules that assign meanings to certain basic symbols and expressions in the language, where the assigned meanings – the interpretations – are actually parts of the structure (e.g., elements or relations). Note that, following the convention of RDFMT, an interpretation of a language statement, as opposed to an interpretation of "certain basic symbols and expressions" is a truth value (true or false), rather than a part or parts of a structure.

Many different structures can be linked to a particular language, provided that the structure is compatible with the language in a well-specified way, ensuring that there is an appropriate correspondence between basic symbols of the language and the basic parts of the structure. (See [29], where the author speaks of this compatibility as a language being "adequate to a structure.")

Notice that some statements are such that they are true under any interpretation of their basic symbols and expressions, in all compatible structures. An example is the statement 'Jane is the mother of John or Jane is not the mother of John', which is traditionally considered to be true under every interpretation of 'Jane', 'John', and 'is_the_mother_of' in all compatible structures. Such a statement is called valid.

The word 'valid' need not always refer to a single statement. It is also frequently applied to a "putative inference" from one statement (or a group of sentences) to another [15]. In this latter use of the word, a valid inference can be seen as a kind of process of moving from the truth of some statement(s) to the truth of another. RDFMT makes frequent use of this sense of the term. In the next section we follow RDFMT and use the word 'entailment' to refer to this second sense of 'valid'.

2.2.2     Entailment

Entailment is the formal counterpart to the intuitive notion of one statement 'following' from others.

It deals with semantics (as opposed to with syntax), because it is concerned with interpretations of expressions and with the truth of statements (composed of those expressions).

Entailment gives us the license to conclude the truth of one statement based on the truth of other statements. Since entailment is concerned with truth values, and since in the model-theoretic approach truth is always defined relative to interpretations, it makes sense that entailment should also be defined in terms of interpretations. We give the definition of entailment after the following example.

Consider the four statements below (which we can suppose could be encoded in a suitably expressive Web markup language):

A.      Jane is the mother of John.

B.       All mothers are females.

C.       No females are males.

D.      Jane is not a male.

It seems intuitively plausible that the statement D in follows in some sense 'as a logical consequence' of statements A, B, and C taken together. But how to make this intuition precise? How can we be sure that we are indeed warranted in claiming that the fourth statement follows logically from the first three? By using the formal relation of entailment as a surrogate for the intuitive notion of logical consequence. (The use of the disjoint groups 'male' and 'female' is based on a similar example used in [13].)

To get an inkling of what needs to be done, consider what it means to say that statements A, B, and C are true. To assert statements A, B, and C amounts to asserting that there is some interpretation IA that makes A true, there is some interpretation IB that makes B true, and there is some interpretation IC that makes C true. Now suppose there is some common interpretation Icommon that can be used for A, B, and C together and that makes all of them true. There may be more than one such common interpretation. If every such interpretation Icommon also makes D true, then we are licensed to conclude that D is a logical consequence of A, B, and C (taken together), since in this case no matter what interpretation we give that makes A, B, and C true, D is also true in that interpretation. In such a case, one says that D is entailed by A, B, and C (taken together).

Roughly speaking, what we have done is set things up so that the entailment of statement D from statements A, B, and C is defined so that the statement D cannot be false, no matter what interpretation Icommon, is used to make A, B, and C true.

This, then, is the definition of the entailment relation (in terms of our example): A statement D is entailed by a group of statements A, B, and C if and only if for any interpretation that makes each of A, B, and C true, that interpretation also makes statement D true.

Entailment is actually a relation between the truth of some statements and the truth of another. This relation is sometimes referred to as the 'consequence' relation, the 'logical consequence' relation, or the 'semantic consequence' relation. Note that we have defined entailment in a particular, technical way, which may be at odds with how this word is used in everyday discourse.

Entailment is "the key idea which connects model-theoretic semantics to real-world applications" [14]. Further,

"If A and B entail each other, then they both 'mean' the same thing, in the sense that asserting either of them makes the same claim about the world. The interest of this observation arises most vividly when A and B are different expressions, since then the relation of entailment is exactly the appropriate semantic licence to justify an application inferring or generating one of them from the other" [14].

It is important to point out that model-theoretic semantics does not by itself directly lead to an operational definition of inference. Instead, it provides a formal definition of entailment which can be used to check the correctness of an appropriate proof theory. The proof theory can then be implemented, often in a fairly straightforward manner.

One subtlety that we have deliberately glossed over is that we have implicitly assumed that the definition of entailment does indeed properly correspond to a single intuitive notion of 'logical consequence.' This assumption is widely made, but its use is not unproblematic [10, 39].

2.2.3     The Abstract Set-theoretic Structure

From the previous discussion of interpretation and entailment, we see that the 'intervening abstract structure' referred to in Section 2.1 does serve an important purpose. It focuses questions about semantics onto a single agreed-upon framework that assigns interpretations to legitimate expressions in a particular language, specifies how to determine the truth values of language statements, and defines entailment in terms of these interpretations and truth values.

The rules governing interpretation are well-defined: to each expression that undergoes interpretation, there is a rule applied to that expression that yields exactly one set-theoretic construct (e.g., an element, function, or relation) corresponding to the expression. If two expressions are mapped to identical set-theoretic constructs, then so far as the model theory is concerned, these two expressions mean the same thing. This fact is similar to the one mentioned in Section 2.2.2, namely, that if two statements A and B entail each other, then they mean the same thing, in the sense that they make identical claims about the world. The difference between these two ways of "meaning the same thing" is that in the former case, what gets interpreted are the elementary components of the language, and the interpretations are actual parts (e.g., terms and relations) of the set-theoretic structure. In the second case, what gets interpreted are statements, and these interpretations, rather than being parts of the set-theoretic structure, are claims about this structure, which may be true or false.

Because the interpretations of legitimate expressions are well-defined, once the model-theoretic conventions and rules of interpretation are agreed upon, the meaning (i.e., the interpretation) of a legitimate language expression is determined. It is no longer a matter of discussion or debate, though the ramifications of this fact can, of course, be a source of debate.

The rules for interpretations can be encoded into software and thus manipulated by machines. For software applications that attempt to exploit the semantics of new markup languages for the Web, entailment is a pivotal notion, since it gives us a formal method of determining when we are warranted in reasoning that one statement 'follows logically' from other statements. It bears repeating that the model-theoretic semantics provides no mechanism in and of itself to implement the inferences; for that, a corresponding implementable proof theory is needed.

2.3     Human versus Machine Interpretations

At the end of the Introduction we mentioned two main views concerning the use of semantics for the Web: one is what might be called the "human-meaningful" approach, and the other is the formal approach to semantics, exemplified by model-theoretic semantics. The differences between these two approaches can perhaps best be understood by exaggerating somewhat the claims of their proponents. (First, note that both groups agree that an appropriate means of conveying meanings is the use of tags from one or more Web markup languages. These tags may or may not travel with the information they describe.)

Proponents of the first view would say that any collection of tags that are meaningful to people can be useful in conducting transactions on the Web. Advocates of the second view would say that a major goal of the Semantic Web is to have computers be able to interpret these tags and make valid inferences about information resources, without having to involve people in the loop. Thus, in the second view, tags and their meanings should form part of a language with a well-defined semantics, so that computers can process the interpretations of these tags to evaluate the truth of language statements and so assess the truth of new statements based on the truth of existing ones.

Typically, though, these two viewpoints are not so starkly held by their proponents. Rather, in many discussions of the Semantic Web, writers frequently combine moderated forms of both views [2, 3, 26]. For instance, within the same article one finds the both of the following: examples of people interacting with Web agents to schedule appointments, and the example of "a hex-head bolt is a type of machine bolt" as an illustration of the kind of information we want to be able to express on the Web using logic [3]. Not only are both views of semantics on display in this  article, but it is also difficult to discern how the logical underpinnings adequate for reasoning with information like "a hex-head bolt is a type of machine bolt" will be sufficient for dealing with the complexity of a human-meaningful activity such as scheduling appointments. This article thus provides a particular example of a more general issue with some popular accounts of the Semantic Web, namely, that in reading such accounts it is often difficult to see how the descriptive and inferential capabilities of the logical languages being developed are sufficient to give software agents the kinds of abilities that some writers suppose they will have.

Further, in at least one case, within the same sentence, one finds both viewpoints intertwined: "The Semantic Web is an extension of the current Web in which information is given well-defined meaning, enabling computers and people to work in better cooperation" [2]. One can see the first view of semantics embedded in the idea that people will need to work cooperatively with computers. The second view of semantics comes through in the phrase "well-defined meaning", which presumably would be obtained via a model-theoretic semantics (though for at least one Web markup language, DAML+OIL, there also exists a so-called 'axiomatic semantics' [13][1]).

This switching back and forth between these two viewpoints of semantics for the Web can be confusing. So, in reading different accounts of the Semantic Web, the onus is on the reader to tease out which view of semantics is being advocated in each part of the discussion. It is important that this teasing out be done, since the issues concerning the appropriate role of each view in a given Web environment differ according to the viewpoint taken and so need to be judged by different criteria.

Developers of the latest languages for the Semantic Web are critically aware of these two views of semantics. Among these developers, issues related to what we have called here the “human-meaningful” view of semantics are frequently discussed under the rubric, “social meaning” (See [25], and discussions on http://lists.w3.org/Archives/Public/www-rdf-comments/, and http://lists.w3.org/Archives/Public/www-webont-wg/).

Although the discussion of social meaning is still evolving, some early positions on these issues are being staked out in papers like [25]. According to this work in progress, for instance, "[h]uman publishers of RDF content commit themselves to the mechanically-inferred social obligations" [25]. Further, the "assertion of an RDF graph G, when G logically entails G', includes the implicit assertion of G'. The implied assertion of G' should be interpreted using the same social conventions that are reasonably used to interpret the assertion of G" [25].

No doubt, issues concerning the interaction between model-theoretic semantics and social meaning will continue to be discussed for some time. Nonetheless, one can identify two central notions underlying the different viewpoints on the use of semantics on the Web: 1) which agreements (conventions) about meanings are made, and 2) who or what will have the responsibility to understand and enforce these agreements. In the human-meaningful view, these agreements can be left either unspecified, or written down in natural language. Proponents of this view might argue that so long as people can successfully interact using mutually-understood conventions, it is fine: individuals bear the responsibility of correctly understanding meanings for their particular purposes. In the formal, model-theoretic view, the agreement about meanings centers on the agreed-upon framework for interpreting language statements in abstract set-theoretic structures. In this case, once people have collectively agreed to use a model-theoretic semantics for a particular language, and have agreed on what this model-theoretic semantics will be, the responsibility for the implementation of 'correct' interpretations of statements in that language lies with machines (and their programmers).

Thus, model-theoretic semantics uses a single unifying framework, instead a potentially infinite set of human judgments about meanings. Given a particular vocabulary, what model theory does is describe "the minimal conditions that a world must satisfy in order to assign an appropriate meaning for every expression in the language" [14]. Of course, to make use of the model-theoretic approach to meanings, people do need to assent to its setup and logical machinery, but it is a single act of assent that can obviate the need for many separate ad-hoc negotiations of agreements concerning truth and entailments.

The next section alerts readers to terminological traps that await them as they attempt to understand different authors' accounts of logic, model theory, and model-theoretic semantics.

3.     TERMINOLOGY

Since there are few if any available introductions to model-theoretic semantics written with an eye toward the Web, readers who want to learn about this topic naturally turn to existing accounts of model theory (see Section 4.1) and model-theoretic semantics. But in doing so they are likely to run across a bewildering variety of usages for certain words, which happen to form part of the lingua franca of authors who write about model-theoretic semantics.

We give three examples of ambiguous usage, corresponding to three major kinds of ambiguity that can trip up readers unfamiliar with the terrain. The first has to do with how, among specialists who write about logic, the same word can be defined in subtly different ways. The second has to do with the same term being defined rather differently across related disciplines (e.g., mathematical logic and computational linguistics). The third deals with the differences that occur between the specific meanings attached to a given term of logic by practitioners in a particular discipline, versus the meaning given to the same term in everyday conversation by people not specializing in that discipline.

These three kinds of ambiguity are, of course, unavoidable. What is important is to be aware that they exist and to develop strategies for dealing with them. Until a guide is written that discusses in some depth the various usages of these terms and how these usages do or do not correspond the those of authors who write about the Semantic Web, the strategy we recommend to readers for dealing with these unavoidable ambiguities is to read widely and constantly compare how different writers use these terms.

3.1     Examples of Ambiguity

We illustrate the three kinds of ambiguity by giving different definitions of the word 'model'.

3.1.1     Differences within a Discipline

The word 'model' is not always defined the same way by logicians who study model theory, though the variability in these definitions is rather slight. Consider the following two definitions, the first taken from an introductory article on model theory, and the second from a textbook on mathematical logic.

Definition 1: "Sometimes we write or speak a sentence S that expresses nothing either true or false, because some crucial information is missing about what the words mean. If we go on to add this information, so that S comes to express a true or false statement, we are said to interpret S, and the added information is called an interpretation of S. If the interpretation I happens to make S state something true, we say that I is a model of S, or that I satisfies S, in symbols ‘I S’ " [19, emphasis in original].

Definition 2: "Now, using induction on formulas φ, we give a definition of the relation I is a model of φ, where I is an arbitrary interpretation. If I is a model of φ we also say that I satisfies φ or that φ holds in I, and we write I φ ... [the long, inductive definition follows]" [8, emphasis in original].

What differs most in these two definitions is the style of definition. The first definition conveys the sense of what a model is, without going the details of a long, inductive definition. Note that in both definitions a model is a special kind of interpretation of a particular statement, an interpretation that stands in the relation of satisfaction to that statement. These ideas relate to the discussion in Section 2.2.1, where we talked of a statement being satisfied in a particular interpretation.

3.1.2     Differences Across Related Disciplines

Compare Definition 2 above to Definition 3 below, which was taken from a textbook on computational linguistics.

Definition 3: "Intuitively a model is a situation. That is, it is a semantic entity: it contains the kinds of things we want to talk about. Thus a model for a given vocabulary gives us two pieces of information. First, it tells us which collection of entities we are talking about; this collection is usually called the domain. Second, for each symbol in the vocabulary, it gives us an appropriate semantic entity, built from the items in D [the domain]. This task is carried out by a function F which specifies, for each symbol in the vocabulary, an appropriate semantic value; we call such functions interpretation functions. Thus, in set theoretic terms, a model M is an ordered pair (D, F) consisting of a domain D and an interpretation function F specifying semantic values in D" [4, emphasis in original].

Note that in Definition 3, a model is defined as an ordered pair, whereas in Definition 2, what is defined is the relation, 'is a model of'. One can easily get the impression that two entirely different things are being defined, but actually the notion underlying both definitions is essentially the same. Although we have taken the definitions out of their respective contexts, the source of the apparent discrepancy is due more to the structure of the definitions (ordered pair versus relation), than to the missing context or to substantial differences underlying the notion of  a 'model'.  For it can be seen that behind both definitions lies the following common idea: some set of vocabulary undergoes interpretation via particular rules. The chief difference between the two definitions is that Definition 2 also includes a specific mechanism (the inductive definition, which we omitted from our quotation) for assessing whether the resulting interpretation satisfies a particular kind of statement (a formula) in that vocabulary.

3.1.3     Differences between Technical and Everyday Usage

The word 'model' as it is used in model theory means something rather different than it does in other everyday uses of the term. A discussion of some of these differences can be found in Suppes [41], where he makes the argument that many scientific uses of this word are actually congruent with its use in model theory. Nonetheless, the following remark by a model theorist is germane.

"The use of the word 'model' in model theory is somewhat different from (and even opposed to) usage in ordinary language. In the latter, a model is a copy or ideal representation of some real object or phenomena. A model in the sense of model theory, on the other hand, is supposed to be the real thing. It is a mathematical structure, and that which it is a model of (a set of axioms, say) plays the role of the idealization" [36].

The catch is that the use of model-theoretic semantics for the Web can naturally lead to another change of perspective concerning the nature and role of models. Specifically, as the discussions concerning the social meaning of statements in RDF/S and OWL show, much of the benefit of using the model-theoretic approach to semantics on the Web will derive from the fidelity with which abstract structures reflect the characteristics of the information resources they are used to model.

3.2     Terms Requiring Further Explication

Readers might test their experience with the following terms, comparing the different usages they encounter when reading different accounts of semantics for the Web:

·           vocabulary, symbol, literal, label, string, term, language;

·           assertion, formula, statement, proposition, sentence, axiom, theory;

·           property, predicate, relation, concept, class, set, role;

·           interpretation, denotation, meaning, semantics, assignment, valuation, truth, satisfaction, structure;

·           entail, imply, infer, deduce, derive, prove;

·           valid inference, consequence, logical consequence, semantic consequence.

Although space here does not permit, there is a need for a fuller explication of the different usages of the above terms.

3.3     Too few words

One way of looking at the difficulties posed by the above examples of ambiguity is that we have too few words at our disposal, and so we must overload them with meanings, which we then must necessarily disambiguate within an appropriate context. One could, of course, try instead to create new words and attempt to fix their meanings. But we do not believe that this approach would help matters. Rather, we simply emphasize that with many words doing double duty and sometimes more, people must read widely and exercise great care in trying to understand how these words are being used. Articles such as [26] are helpful in calling attention to the meanings of words and concepts from disciplines with close connections to the Semantic Web.

4.     PHILOSOPHY

Some of the difficulties encountered by the non-expert in understanding model-theoretic semantics for the Web may be due to a lack of context in which to view the more traditional uses of model theory and semantics, especially in disciplines such as mathematics, linguistics, philosophy, and computer science. This section provides some context for these traditional uses, along with references to some appropriate literature.

4.1     Model Theory

Model theory is a branch of mathematical logic that deals with 'truth in a structure' [22, 29, 36], where by 'structure' is meant a set-theoretic structure, that is, a set together with particular relations and functions defined on it, along with certain constants elements distinguished in the set [21].

More broadly speaking, model theory is "the study of the interpretation of any language, formal or natural, by means of set-theoretic structures, with Alfred Tarski's truth definition as a paradigm." [19]

Considering just these descriptions of model theory as a branch of mathematical logic, it is not at all obvious why model theory should be relevant to the Semantic Web. But, as we have shown above, when model theory is used to provide a model-theoretic semantics for some language that is used to describe information resources, it lets us assign well-defined interpretations to legitimate language expressions (that are supposed to describe these resources) and to make inferences with statements that describe these resources.

When model theory is used in mathematics, the semantics of a language is used to reason about mathematical structures, and the interpretations of the semantics do not need to make sense for any world outside that of the abstract structures themselves.

However, when model-theoretic semantics is used in a context like the Semantic Web, where people may well want the semantics they use in their markup languages to have some connection with the real world as they know it, certain difficulties can arise, perhaps because people expect more of the semantics than it purports to give. As mentioned in Section 2.2, model-theoretic semantics has nothing directly to say about the connections between the abstract structures it deals with and any aspects of the real world that lie outside this structure. People will often make such connections, especially considering that they want to the formal semantics to be about information resources that can be pointed to on the Web, but the model-theoretic semantics by itself does not.

The move from model theory as a tool of mathematical logic for investigating mathematical structures to model-theoretic semantics as a tool for describing real-world resources (named with urirefs or literals) is a shift in emphasis, but it is one that model theory can accommodate, provided that people who use it do so with expectations that are consonant with its capabilities.

Logicians who use model theory in mathematics are often interested in certain kinds of questions about mathematical structures, such as how they can be classified and constructed. Those who use model-theoretic semantics in artificial intelligence are often concerned with the expressiveness and tractability of the languages for which they provide a semantics. For the creators of the most recent Semantic Web languages, the expressive and computational characteristics of these languages are certainly important issues to be considered. It remains to be seen, though, which other kinds of questions/constraints dealing with the models of these languages will be of interest to researchers and developers of the Semantic Web.

4.2     Different Presentations

The presentation of the model-theoretic semantics for Web markup languages differs from the presentation "classical model theory" of first-order languages [18].

Hodges remarks that "[p]articular kinds of model theory use particular kinds of structure; for example mathematical model theory tends to use so-called first-order structures, model theory of modal logics uses Kripke structures, and so on" [19].

The structures used by RDFMT and the model theory for OWL may look rather peculiar when compared to first-order or Kripke structures.

One reason the model theory in RDFMT looks different from first-order model theory is that the interpretation of a relation symbol in RDFMT is not a simple relation, as it is in first-order model theory. This fact was alluded to in Section 2.2.1, where we mentioned that the way RDFMT interprets relation symbols is rather more complicated than the way we interpreted 'is_the_mother_of' in our example.

The model theory for OWL is strikingly different from the model theory for a basic modal logic or description logic, even though, as a language, OWL has strong influences from description logics [1, 30, 33]. One reason for this difference is that OWL contains many features not usually found in basic description logics [1, 30, 33].

The fact that the presentations of the semantics for RDF/S and OWL differ rather strikingly from classical presentations of model-theoretic semantics for the language of first-order logic is another reason why readers can have a particularly difficult time understanding the semantics of these latest Web markup languages.

4.3     A Context for Semantics and Models

In this section we give some pointers to works on semantics and models from more general perspectives, to give readers a broader context for understanding model-theoretic semantics on the Web.

4.3.1     Semantics

Introductory treatments of semantics from the linguistic and philosophical perspectives can be found in [28, 42]. A more detailed exposition is [24]. A cross-disciplinary treatment of semantics combining the linguistic, philosophical, and computer-science perspective can be found in [37].  For perspectives from computational linguistics and artificial intelligence, see [4] and [7], respectively.

For overviews of the breadth and depth of semantics as it relates to programming languages, see [16] and [31].

For introductory expositions of model theory from the perspective of mathematical logic, see [11], [15], [17-20], [22], [36]. For more-detailed treatments see [8], [9], [12], [21], and [29].

There is also an extensive literature on semantics from the perspective of the database community. An appropriate place to cite this work would be in a discussion relating to the implementation of model-theoretic semantics on the Web.

4.3.2     Models

A recent book by Suppes [41] discusses models in science from the perspective of representation and invariance of scientific structures. For a recent monograph on the model-theoretic perspective in science, see [38].

5.     SUMMARY AND CONCLUSION

5.1     Summary

Model-theoretic semantics is a formal account of the meanings of legitimate expressions in a language. It has its roots in model theory, a branch of mathematical logic that deals with the notion of truth in a structure. The "account of meanings" that model-theoretic semantics provides is limited to interpreting legitimate expressions of a particular language in compatible set-theoretic structures, and to assessing whether certain statements in that language are true in those structures. The model-theoretic approach makes no attempt to relate its set-theoretic constructs (elements, functions, relations) to the outside world. Thus, it does not look beyond its abstract set-theoretic structures to deal with what has been called 'social meaning' or to address issues concerning the intrinsic nature of the resources it describes. Whether the correspondence between these abstract structures and the aspects of the real world that they represent is acceptable for the purposes at hand is an assessment that must be made by people, outside the framework of model-theoretic semantics itself.

There is no special magic to the model-theoretic approach, at least not with respect to the "real meanings" of expressions on the Web. People still need to agree on the conventions of how expressions are to be interpreted. The virtue of the model-theoretic approach to semantics is that it focuses the conventions for dealing with meanings onto a consolidated framework that provides the rules for assigning well-defined interpretations to language expressions, as well as a mechanism for determining when one statement is entailed by other statements.

Such a framework, when complemented with a suitable, implementable proof theory, can be used to perform automated reasoning over the Web. Since a major impetus for developing the Semantic Web is to allow machines to do limited forms of automated reasoning without human intervention, the model-theoretic approach to meanings is well suited to this endeavor.

Although some of the difficulties encountered by people trying to understand model-theoretic semantics are inherent in the abstract and intricate nature of the subject itself, other obstacles are also part of the problem. Among these obstacles are:

·           the use of ambiguous basic terminology in different accounts of logic and model theory;

·           a lack of accessible descriptions of model theory outside the realm of mathematical logic (notable exceptions are RDFMT itself, the articles by Hodges, and the draft book by Blackburn and Bos, listed in the bibliography);

·           an incomplete account of the relation of the model-theoretic approach to semantics for the Web and similar approaches to semantics in related disciplines (e.g., linguistics, computer science).

The use of model-theoretic semantics for recent Web markup languages can be seen as the beginning of an attempt to make a limited form of artificial intelligence viable on the Web.

5.2     Conclusion

By giving an introductory explication of certain fundamental issues concerning the roles and limitations of model-theoretic semantics for the Web, we have shown that a number of topics require further, detailed exposition if users and developers are to make informed choices about how they deal with meanings on the Web. Among these topics are: 1) the rationale for using model-theoretic semantics on the Web; 2) the differences between model-theoretic semantics and 'social meaning' on the Web; 3) the difficulties arising from the non-uniform use of vocabulary for discussing issues of logic; and 4) the relationship of the model-theoretic approach for semantics on the Web to its use in other, related disciplines.

The Semantic Web is in its infancy. For it to mature, an entire foundation needs to be built, consisting not just of an assortment of Web markup languages, each with its own semantics, but also of a broader base of knowledge and tools geared toward promoting the widespread understanding and appropriate use of these languages. Creating this knowledge and these tools will require in-depth treatments of the key conceptual and implementation issues concerning model-theoretic semantics for the Web. A core issue that will not disappear is the relationship between the use of model-theoretic semantics and what [25] calls the interaction between social and formal meaning.

Currently, the experts at the fore of these developments have ways of modulating and demodulating conversations among themselves that help to clarify the vocabulary and issues involved. Soon, what will be needed is a sort of modulation/demodulation framework where questions and answers from non-expert users can be appropriately asked and adequately answered. Ideally, the Semantic Web itself could be used to create such a modulation/demodulation framework. In the interim, we hope that this paper makes a positive contribution by encouraging wider and deeper discussions of core issues.

Most basic accounts of model-theoretic semantics are written by logicians for students studying logic or computer science. Given that the use of model-theoretic semantics is bound to affect a much wider group of people than just students in logic and computer-science courses, it would be very useful to have new expositions written that are aimed at a broader audience of Web users and developers.

6.     ACKNOWLEDGMENTS

This work was partially supported by a grant from the National Imagery and Mapping Agency under grant number NMA401-02-1-2009 and by a University Graduate Research Assistantship from the University of Maine. Thanks to Patrick Hayes for valuable discussions about RDF Model Theory, to Peter Patel-Schneider for substantive contributions to earlier drafts, and to the anonymous reviewers for their useful suggestions for improvement.

7.     REFERENCES

[1]     Baader, F.; Nutt, W.; Basic Description Logics in F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider (Editors), The Description Logic Handbook. Cambridge University Press, 2002, 47-100.

[2]     Berners-Lee, Tim; Miller, Eric. The Semantic Web lifts off. ERCIM News, Number 51, October 2002, 9-11, http://www.ercim.org/publication/Ercim_News/enw51/berners-lee.html .

[3]     Berners-Lee, T.; Hendler, J.; and Lassila, O. The Semantic Web. Scientific American 184(5), 2001, 34-43.

[4]     Blackburn, Patrick; Bos, Johan. Representation and Inference for Natural Language: A First Course in Computational Semantics. http://www.comsem.org

[5]     Brickley, Dan; Guha, R. V. (Editors), RDF Vocabulary Description Language 1.0: RDF Schema, W3C Working Draft 23 January 2003, http://www.w3.org/TR/rdf-schema

[6]     The Concise Oxford Dictionary of Linguistics. Oxford, 1997.

[7]     Davis, Ruth. E. Truth, Deduction, and Computation: Logic and Semantics for Computer Science. Computer Science Press, 1989.

[8]     Ebbinghaus, H.-D.; Flum, J.; Thomas, W. Mathematical Logic. 2nd edition. Springer, 1994

[9]     Enderton, Herbert B. A Mathematical Introduction to Logic, 2nd ed., 2001.

[10]  Etchemendy, John.The Concept of Logical Consequence. CSLI 1999.

[11]  Etchemendy, John; Barwise, Jon. Model-theoretic Semantics, in Posner, Michael (Editor), Foundations of Cognitive Science, MIT Press, 1989, 207-243.

[12]  Feferman, Solomon. Tarski's Conceptual Analysis of Semantical Notions. Expanded text of a lecture for "Sémantique et épistémologie" Casablanca, 2002.  http://math.stanford.edu/~feferman/papers/conceptanalysis.pdf.

[13]  Fikes, Richard and McGuinness, Deborah L., An Axiomatic Semantics for RDF, RDF Schema, and DAML+OIL, KSL Technical Report KSL-01-01, 2001. Updated October, 2001. http://www.ksl.stanford.edu/people/dlm/daml-semantics/daml+oil-axioms-october2001.htm.

[14]  Hayes, Patrick (Editor) RDF Semantics. W3C Working Draft 23 January 2003, http://www.w3.org/TR/rdf-mt/.

[15]  Hintikka, J. Is There Compeleteness in Mathematics after Gödel?, Philosophical Topics 17(2), 69-90, 1989.

[16]  Hoare, C. A. R.; Jifeng, He. Unifying Theories of Programming. Prentice Hall, 1998.

[17]  Hodges,Wilfrid. The unexpected usefulness of model theory in semantics. Conference on Semantics and Epistemology, Casablanca, March, 2002. http://www.maths.qmw.ac.uk/~wilfrid/casablanca.pdf.

[18]  Hodges, Wilfrid. First-Order Model Theory. Stanford Encyclopedia of Philosophy. http://plato.stanford.edu/entries/modeltheory-fo/ 2001.

[19]  Hodges, Wilfrid. Model Theory. Stanford Encyclopedia of Philosophy. http://plato.stanford,edu/entries/model-theory/ 2001.

[20]  Hodges, Wilfrid. Classical Logic I: First-Order Logic, in Goble, Lou (Editor), The Blackwell Guide to Philosophical Logic, 2001, 9-32.

[21]  Hodges, Wilfrid. A Shorter Model Theory. Cambridge, 1997.

[22]  Hodges, Wilfrid. Truth in a structure. Proceedings of the Aristotelian Society, New Series, 86 (1985/1986), 131-151.

[23]  Horrocks, Ian. DAML+OIL: a Reason-able Ontology Language for the Semantic Web. Keynote talk given at AISB 2002, London, http://www.cs.man.ac.uk/~horrocks/Slides/aisb02prn.pdf.

[24]  Jackendoff, Ray. Foundations of Language: Brain, Meaning, Grammar, and Evolution. Oxford, 2002.

[25]  Klyne, Graham; Carroll, Jeremy J. (Editors) Resource Description Framework (RDF): Concepts and Abstract Syntax. W3C Working Draft 23 January 2003, http://www.w3.org/TR/rdf-concepts.

[26]  Lassila, Ora; McGuinness, Deborah. The Role of Frame-Based Representation on the Semantic Web. http://www.ida.liu.se/ext/epa/cis/2001/005/paper.pdf

[27]  Lassila, Ora; Swick, Ralph R. (Editors.), Resource Description Framework (RDF) Model and Syntax Specification, W3C Recommendation 22 February 1999.

[28]  Löbner, Sebastian. Understanding Semantics. Arnold/Oxford, 2002.

[29]  Manzano, María. Model Theory. Oxford, 1999.

[30]  McGuinnes, Deborah L.; van Harmelen, Frank. Web Ontology Language (OWL): Overview. W3C Working Draft February 5, 2003, http://www.w3.org/TR/owl-features/

[31]  Meyer, Bertrand. Introduction to the Theory of Programming Languages. Prentice Hall, 1991.

[32]  Mosterίn, Jesús, in Preface to Manzano, Maria, Model Theory. Oxford, 1999.

[33]  Nardi, D.; Brachman, R. J. An Introduction to Description Logics. In the Description Logic Handbook, edited by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider, Cambridge University Press, 2002, 5-44.

[34]  Oullett, Roxane; Ogbuji, Uche. Introduction to DAML: Part I. http://www.xml.com/pub/a/2002/01/30/daml1.html

[35]  Patel-Schneider, Peter F.; Hayes, Patrick; Horrocks, Ian (Editors), Web Ontology Language (OWL) Abstract Syntax and Semantics. W3C Working Draft 3 February 2003, http://www.w3.org/TR/owl-semantics/.

[36]  Pillay, Anand. Model Theory. Notices of the American Mathematical Society, December, 2000, pp. 1373- 1381. http://www.ams.org/notices/200011/fea-pillay.pdf.

[37]  Rastier, François; Cavazza, Marc; Abeillé, Anne. Semantics for Descriptions: From Linguistics to Computer Science. CSLI, 2002.

[38]  Ruttkamp, Emma. A Model-theoretic realist interpretation of science. Kluwer, 2002.

[39]  Shapiro, S. Necessity, Meaning, and Rationality: The Notion of Logical Consequence, in Jacquette, Dale (Editor). A Companion to Philosophical Logic. Blackwell, 2002, 227-240.

[40]  Smith, Michael K.; McGuinness, Deborah; Volz, Raphael; Welty, Chris.  Web Ontology Language (OWL) Guide Version 1.0. W3C Working Draft 4 November, 2002, http://www.w3.org/TR/owl-guide/.

[41]  Suppes, Patrick. Representation and Invariance of Scientific Structures. CSLI, 2002.

[42]  Swart, Henriëtte de. Introduction to Natural Language Semantics. CSLI, 1998.


 



[1] As pointed out by a reviewer, this is really an axiomatization of DAML+OIL in a variant of first-order logic, and thus is a two-phase way of providing semantics.