|
|
| ABSTRACTS |
|---|
|
|
|
| ABSTRACTS |
|---|
The abstracts are also available as downloadable compressed Word documents, for
Winword 6.0 or
Word for Macintosh 5.0.
Semantically, we first look at how focus can have both a truth-conditional and a pragmatic effect thereby reviewing a set of focus-sensitive phenomena (free focus, focus sensitive operators, adverbial quantification). We then consider and compare three alternative theories of focus semantics namely, Rooth's alternative semantics, Krifka's structured meanings approach and the Higher-Order Unification treatment.
Syntactically, the focus is on the issue of focus projection: given a prosodically marked element, how can the syntactic focus be derived? After examining data from both English (a fixed word order language) and German (a semi-free word order language), we compare Selkirk's theory of focus projection with the HPSG approach proposed by Enghdahl and Valduvi.
Throughout the course, emphasis will be on (i) identifying the empirical issues, (ii) underlining the basic ideas of the accounts proposed to solve these empirical problems and (iii) comparing the linguistic adequacy of the alternative treatments being considered.
Prerequisites for the course are a working knowledge of Montague grammar and some acquaintance with basic syntax theory and HPSG.
LITERATURE:
Elisabet Engdahl and Enric Vallduvi. 1994.
Information packaging and grammar architecture: a constraint-based
approach.
In DYANA-2 Report R1.3.B, ILLC, Amsterdam.
Claire Gardent and Michael Kohlhase. 1996. Focus and Higher-Order Unification. Proceedings of COLING 1996, Copenhagen.
Ray Jackendoff. 1972. Semantic Interpretation in Generative Grammar. The MIT Press
Manfred Krifka. 1992. A compositional semantics for multiple focus constructions. In Joachim Jacobs (ed.), Informationstruktur und Grammatik, Sonderheft 4.
Mats Rooth. 1992. A Theory of Focus Interpretation. Natural Language Semantics, pages 75-116.
E. Selkirk. 1984. Phonology and Syntax. The relation between sound and structure. MIT Press, Cambridge.
The course will give students experience with concepts like bisimulation and coinduction. This will strengthen their understanding of induction. In work on circularity and logics of knowledge, the key ideas of modal logic and of the game-theoretic semantics of logic will come up. On a different pedgagogic note, students will see what it is to do LLI work which both has mathematical content and leads to interesting applications.
The course will be based in part on the just-completed book by Jon Barwise and Larry Moss.
Tentative outline of the course:
I.Introduction: Informal development of some central ideas and concepts, philosophical and mathematical motivations, related approaches.
II.The syntactical framework: The logic of partial terms, basic axioms of applicative theories, specific applicative theories for various purposes. Construction principles for variable types.
III. Models for applicative theories: Recursion-theoretic models, term models, generated models. Models for theories of variable types over applicative models.
IV. Proof theory: A survey of some results which illustrate the relationship between the considered theories and more usual systems of first and second order arithmetic and type theories.
V. Applications: Some directions of application to mathematics, theoretical computer science and linguistics. Relationship of the variable types approach to polymorphic constructions in the latter two areas.
The course will attempt a systematic presentation of the existing results on reflection principles applicable in the study of fragments of first order Peano arithmetic PA. Main topics to be dicussed:
Monday
16h45 - 17h30: Renate Schmidt, Decidability by resolution
for many modal logics.
17h30 - 18h15: Angelo Montanari, A Set-Theoretic Translation
Method for Polymodal Logics.
Tuesday
16h45 - 17h30: Thomas Fuchss, Integrating Processes in
Temporal Logic.
17h30 - 18h15: Stephane Demri, The complexity of some logics
with relative operators.
Wednesday
16h45 - 17h30: Philippe Balbiani, A promenade from arrow logic
to boolean modal logic.
17h30 - 18h15: Tomasz Kowlaski, Semisimple varieties of
boolean algebras with conjugate normal operators.
Thursday
16h45 - 17h30: Takahito Aoto, On the finite model property
of extensions of MIPC.
17h30 - 18h15: Alexander Kurz: A note on the frame semantics
of modal logics.
Friday
16h45 - 17h15: Carsten Grefe, On the finite model property
of Fisher Servi's intuitionistic modal logic
and some of its extensions.
17h15 - 17h45: Dimitry Tishkowsky, Polymodal deductive systems for
predicate superintuitionistic logics.
17h45 - 18h15: Vladimir Spanopulo,
On the verification of PLTL Satisfuiability by
means of boolean domains.
- encodings of basic concurrent data and control structures
- concurrent objects
- behavioral equivalences and simple reasoning about programs
- static type systems
- extensions of the pi-calculusfor physical distribution, process migration, and fault tolerance.
Examples will be drawn from our experience with Pict, a programming language based on the pi-calculus.
We first investigate the traditional application of set constraints which has been the ``set-based'' type analysis for imperative and declarative programming languages. We will then present a new schema of using set constraints for the solving of constraint problems over trees, and in particular feature trees. One application is the dynamic pruning of search space with set constraints statically derived from the constraint-solving program. We use a connection between set-based analysis and abstract interpreation for proving correct this schema. We conclude by exhibiting concrete applications in computational linguistics which subsume already existing techniques using finite-state automata for more efficient processing of, for example, HPSG grammars.
1) Computation and Logic: the paradigm of logic programming - programs=theories, computation=proof search - From G\"odel's completeness theorem to the procedural interpretation of logic programs - Constraint languages and G\"odel's incompleteness theorem - The class of Concurrent Constraint Logic Programming languages CLP(X) 2) Examples and demonstrations of CLP(X) programs - CLP(H)-Prolog: deductive databases, list processing, meta-interpreters, theorem proving - CLP(lambda): higher-order theorem proving - CLP(R): linear programming and complex system modeling. - CLP(FD): constraint propagation algorithms and combinatorial search problems. 3) Formal semantics of CLP(X) languages - Why? Observable properties and equivalences of programs - The programming language versus theorem prover points of view - Full abstraction theorems between operational and fixed point semantics - Program analysis by abstract interpretation - Completeness theorems w.r.t. the logical semantics.
In this course, we will cover the following topics:
1. Programming language: Searls' string variable grammars.
2. Algorithms: local and global (nucleotide and protein) sequence alignment algorithms, constructing the physical map of a chromosome by STS-probe orderings using Booth-Lueker p-q trees, construction of phylogeny trees, alignment logic.
3. Modeling: protein folding on lattice models (Monte Carlo with Gaussian contact energy function as in Karplus et al., string properties as in Istrail et al.), Hidden Markov Models for pattern recognition (as in speech recognition and in recognizing promoter sequences in DNA), constraint-based topology prediction (from NMR-data as in Altman et al., secondary structure prediction as in Rawlings et al.)
We introduce the family of (concurrent) constraint logic programming languages by giving various calculi and by examples. Constraint Handling Rules are a special purpose language that will allow us to specify and implement constraint solvers at a high level of abstraction. In this way, we will present the most common constraint domains and their application areas by example: Boolean constraints for e.g. circuit design, linear polynomial equations for e.g. financial and engineering applications and finite domains for scheduling. Depending on the interests of the attendees, we my also present constraint systems for e.g. temporal or terminological reasoning. Finally, we will examplify with two applications studies that real-life problems are chracterized by a heterogeneous mix of both common and application-specific constraint systems. One application is a tool for optimzing the placement of transmitter stations for wirless communication, the other one an internet tool that allows users to calculate the estimated fair rent of their apartment.
Course outline:
1. Introducing Constraints
2. Constraint Logic Programming
3. Constraint Handling Rules
4. Constraint Domains (Booleans, Numbers, Finite Domains, and more)
5. Applications by Example
NOTE: The course would greatly benefit from demonstrations shown live on a computer (a SUN Workstation) using ECLiPSe, ECRC's advanced constraint logic programming platform. The course is based on a lecture on the same topic given at the University of Munich.
Prof. Achim Jung (University of Birmingham, UK) Incomplete information in databases Elena Ravve (Technion, Israel) Database normal form, schema transformations and preservation of dependencies Duminda Wijesekera (University of Minnesota, USA) Normal forms and a syntactic completeness theorem for functional independencies T. Sentissi, E. Pichat (Lyon) Object Oriented Database design with Normalized Semantic Graph Gill Dobbie (Victoria University, New Zealand) Investigating normalisation in object-oriented databases Laura Felice (Universidad Nacional del Centro, Argentina) Schema updates in OODB X. Delannoy (Grenoble), C. Del Vigna (Paris) Integrity vs Confidentiality, An Occurrence of Galois Lattices Harald Kosch (Lyon - Klagenfurt) Theoretical considerations on the correct representation of parallel relational query processing. Natasha Alechina (University of Birmingham) Semi-structured information and generalised schemes. Unconfirmed: Janusz R. Getta (University of Wollongong, Australia) Query Processing in Database Systems with Inconsistent Information Ana Maria Simonet and Michel Simonet (IMC-IMAG laboratory) THE OSIRIS VIEW SYSTEM
Specifically:
-- Constructions in a category: The standard constructions of products, coproducts, exponents, limits, colimits, list objects and universal relations will be presented with examples of how they apply in formalizations of linguistic theory.
-- Universals as methodology: The category theoretic notion of a universal arrow, representing a kind of optimality of construction within a category, will be considered as a methodological device yielding formal "reasons for abstraction."
-- Representations: Duality theorems, connecting "proof theory" to "model theory," will be discussed as a tool in the design of a logic to match "intended models" and in the construction of models to yield completeness theorems for a logic.
-- Connections to Categorial Grammar: Although the word "category" is used in distinct technical senses within categorial grammar and category theory, there are significant connections between these to fields. These connections will be considered as they arise in other discussion.
"Belief revision" is the name of a rapidly growing field of interest to, among others, epistemology and philosophy of science on the one hand and theoretical computer science on the other. To a remarkable extent the growth has been influenced by the seminal work of Alchourron, Gardenfors and Makinson (AGM). This course would offer an introduction to the theory of belief revision by concentrating on AGM, first presenting that theory and then discussing select criticisms, emendations, and alternatives.
The presentation of AGM would emphasize model theory, starting with Grove's semantics and continuing with Segerberg's doxastic dynamic logic. Topics might include contributions associated with the names of Spohn, Lindstrom & Rabinowicz, Lehmann, Lehmann & Freund, Pearl, Darwiche & Pearl, Pearl & Goldszmidt, and perhaps others.
PREREQUISITES A course in elementary logic. Some background in modal logic would be helpful.
READINGS Handouts would be prepared and distributed at the beginning of the course.
In addition to the theoretical interest, which consists in the use of the language of mathematics as a kind of laboratory of linguistics, there are practical applications of the theory in the form of natural-language interfaces to formal systems, such as mathematical proof editors. Such interfaces have been implemented, at least, for English and French.
E. Zimmermann, J. van der Does, J. Groenendijk and M. Stokhof, W. Zadrozny, Oesten Dahl and Christina Hellman, L. Kalman, J. Pelletier, Barry Smith, H. Kamp, B. Partee, T. Janssen, P. Pagin and D. Westerstaahl, J. Hintikka, S. Neale, J. van Benthem, M. Kanazawa, E. LePore, G. Segal
11.8 Theo Janssen, Amsterdam: The principle of compositionality: a criterium for understanding
Dag Westerstahl, Stockholm Compositionality in the big picture
12.8 Josh Dever, Berkeley Compositionality as methodology
Thomas Hofweber, Stanford Does a compositional semantics play an explanatory role?
13.8 Herman Hendriks, Utrecht Homomorphisms and Many-Sorted Algebras
Sean Fulop/Ed Keenan, UCLA Compositionality: A Global Perspective
14.8 Christina Hellman, Stockholm The compositionality principle and substitution operations in natural discourse
Östen Dahl Is the result of interpreting a linguistic expression utterance a uniquely determined object?
15.8 Peter Pagin, Stockholm Compositionality: epistemology and mathematics
Theo Janssen, Amsterdam: Frege and the principle of compositionality
ABSTRACTS
Theo Janssen, Amsterdam: The principle of compositionality: a
criterium for understanding
Phenomena in natural language semantics can be complicated.
Therefore it is not surprising that sometimes complex logical languages are used,
and that complex manipulations on logical formulas arise. The principle of
compositionality of meaning puts some borderlines on the
possibilities:
1) Each constituent of the natural or logical language should have a
meaning.
2) Each operation on formulas should represent an operation on
meanings.
If it is not obvious whether a proposal is within these borderlines,
the principle challenges us to change the situation. Of each of the two
cases an example will be discussed:
1) A classical example of a complex operation on formulas.
The original rule from Montague's PTQ for relative clause formation
was incorrect. A correction by Thomason was mentioned in the collected
philosophical work of Montague. The correction is a form of complex
formula manipulation. It will be shown that the search for a
compositional rule yields a simpler and better understandable solution.
2) A recent example from work by Wilfrid Hodges.
In game theoretical semantics (a la Hintikka) formulas have a meaning
which is not formed from the meanings of its parts. It is claimed by
Hintikka that a compositional interpretation is not possible, and also
argued that it is not desirable. The compositional semantics desiged by
Hodgeswill be presented, and the insights obtained from that will be
discussed.
In both cases the violation of compositionality can be considered as
an indication that the semantic side of the situation is not well
understood. Designing a compositional solution stimulates a proper investigation of
the situation.
Dag Westerstċhl, Stockholm Compositionality in the big picture
In the context of natural languages, the principle of
compositionality is appealed to (or denied) within at least three rather different
enterprises:
(1) presenting a formal semantics; (2) accounting for actual language
understanding; (3) giving a philosophical theory of meaning. I will try
to assess the place of the principle in each of those enterprises. In the
process, I try to spell out how compositionality can be justified and
indispensable even though only a *part* of 'the big picture' of linguistic
communication.
Josh Dever, Berkeley Compositionality as methodology
This paper examines a recent result of Zadrozny's, purporting to show that
any meaning function can be 'encoded' as a compositional meaning
function. I show that the success of Zadrozny's encoding technique depends on an
objectionably weak understanding of how the new compositional meaning
theory is to correspond to the original noncompositional meaning
theory. I then show that Zadrozny shifts his standards of correspondence when
discussing systematicity as a constraint on meaning theories, and that
if he had held to his original standards, he could also have shown that
anymeaning theory could be encoded as a systematic meaning theory. I
conclude that the route to a methodologically useful respect for
compositionality lies not in constraints on the type of mapping from syntax to
semantics, but in a stricter correspondence condition between pretheoretic
assignments of meanings to strings and final theoretic assignments of meanings to
those same strings. I conclude by arguing that those who take a semantic
theory to be constrained by the data only at the sentential level are in a
poor position to appeal to compositionality as a principle for choosing
among meaning theories.
Thomas Hofweber Does a compositional semantics
play an explanatory role?
There are two main issues about compositional semantics for
natural language. They are rather independent and unfortunately they are not
always kept apart in discussions of the problem. These issues are:
1) Do natural languages have a compositional semantics?
2) Does a compositional semantics play an explanatory role?
It seems that if the answer to 2) is yes then the answer to 1) should
be yes, too. But the other way round it is certainly not clear. If one
believes that the answer to both is yes then it might also be the
case that only some kinds of compositional semantics can play this
explanatory role. If one believes that the answer to 2) is yes then one should be
interested in what kind of compositional semantics can play this
explanatory role. The kinds obtainable through certain triviality
results might not qualify.
In my talk I will give a critical survey of recent discussion about
2), in particular of work arising from Stephen Schiffer*s claim that the
answer to 2) is no. To see whether this claim is defensible we will have to
consider what explanatory tasks there are in which a compositional
semantics might play are role. It seems to me that there are
basically two:
a) An explanation of semantic competence.
b) An explanation of cognitive competence.
I will consider Schiffer*s attempt of an explanation of each one of
them without taking recourse to any kind of semantic theory. I will try to
point to some weaknesses in his arguments, I will try to say how the
proposed explanations will differ from one*s using compositional
semantics and I will try to point to advantages that explanations without
semantics have over ones with semantics. Finally, I will make connections to
attempts to answer question 1).
Herman Hendriks, Utrecht Homomorphisms and Many-Sorted
Algebras
The present paper studies the general implications of the
principle of compositionality for the organization of grammar. It will be argued
that Janssen's (1986) requirement that syntax and semantics be *similar*
algebras is too strong, and that the more liberal requirement that syntax be
*interpretable* into semantics leads to a formalization that can be
motivated and applied more easily, while it avoids the technical complications
that encumber Janssen's formalization. Moreover, this alternative
formalization even allows one to further `complete' the formal theory of
compositionality, in that it is capable of clarifying the role played
by *model-theoretic interpretation* and *meaning postulates*, two aspects
that received little attention in Janssen (1986) and Montague (1970).
Sean Fulop/Ed Keenan, UCLA Compositionality: A Global
Perspective
Recent work from diverse points of view (e.g. Keenan and Stabler
1995, 1996; Kalman 1995; Zadrozny 1994) has called into question the
empirical force of Compositionality as a constraint on the
interpretation of natural languages. There is even perhaps something
of a consensus that Compositionality as standardly formulated is too
weak, allowing too great a range of possible interpretations.
But, as is clear from the detailed presentation in Janssen (1997),
there is considerable difference as to precisely where the problems
lie and precisely what modifications should be imposed.
Here we propose a modest strengthening of Compositionality, one that
has, we feel, always been tacitly assumed though not consciously
intended. We call this strengthening Global Compositionality (GC).
We provide a formal statement of Standard Compositionality which makes
its shortcoming clear: it does not constrain the class of models
(construed as pairs (E, m) consisting of a universe E and an
interpretation function m) which may be used to interpret a language,
but only provides a local condition on each model in turn.
We then consider Strong Compositionality, a condition proposed by
Keenan and Stabler (1996). SC provides a constraint on the class of
interpretations available to each model with a given universe E; it is
no longer a purely local condition on a single model. Yet, we find
that SC is not sufficient; the condition says nothing against making
an interpretation dependent on properties of the universe in its
model---any properties.
To remedy these problems, a further strengthening of Compositionality
is proposed: Global Compositionality. We show that GC provides the
proper degree of constraint on the variation of semantic
interpretation from one model to another, while not ruling out certain
desirable kinds of dependencies on the nature of the universe.
References:
Janssen, Theo. 1997. "Compositionality." In Handbook of Logic and
Language, J. van Benthem and A. ter Meulen (Eds.)
pp. 417--473. Elsevier Science.
Kalman, Laszlo. 1995. "Strong Compositionality." Booklet, Research
Institute for Linguistics, Hungarian Academy of Sciences.
Keenan, E. L. and E. P. Stabler. 1995. "There is more than one
language." In Langues et Grammaire, L. Nash and G. Tsoulas (Eds.) pp.
217--235.
Departement des Sciences du Langage, Universite de Paris.
Keenan, E. L. and E. P. Stabler. 1996. "Abstract syntax." In
Configurations, Anna-Maria Di Sciullo (Ed.) pp. 329--344. Cascadilla
Press.
Zadrozny, Wlodek. 1994. "From compositional to systematic semantics,"
Linguistics and Philosophy 17:329--342.
Christina Hellman, Stockholm The compositionality principle and
substitution operations in natural discourse
A number of phenomena in natural language interpretation do not
easily go together with a standard formulation of the theory of semantic
compositionality.
I shall discuss a class of cases that overtly seem compatible with
this principle, viz. substitution operations in natural discourse, and I
will argue that they in fact are not. The interpretation of an expression
such as 'vice versa' would seem to consist in a simple switch of two elements
in a sentence, as in (1), paraphraseable as (2):
(1) A rationally managed agriculture is a prerequisite for a
developed industry and vice versa.
(2) A rationally managed agriculture is a prerequisite for a
developed industry and a developed industry is a prerequisite for a rationally
managed agriculture.
However, the actual use and interpretation of 'vice versa' forces us
to redefine the interpretation procedure in a way that no longer makes it
compatible with the compositionality principle.
Östen Dahl, Stockholm: Is the result of interpreting a linguistic
expression utterance a uniquely determined object?
In a well-behaved compositional system, the output of semantic
interpretation as applied to an expression E1 should be some unique
object that you can use as input when interpreting another expression E2 which
E1 is a constituent of. Similarly, the result of interpreting an
utterance U should be a unique object that we can act upon in various ways. Thus,
declarative sentences are usually seen as expressing propositions that
the participants of the conversation may entertain and express attitudes
towards. In this paper, I shall return to a possibility I discussed in
some papers I wrote a very long time ago, viz. that expressing an attitude
towards something that someone has uttered involves an act of
abstraction that creates an object, not necessarily uniquely determined. Phenomena
that will be discussed in this context include intensionality, "sloppy
identity" and vagueness.
Peter Pagin, Stockholm: Compositionality: epistemology and
mathematics
How can we justify the claim that the principle of
compositionality is valid for natural languages? And given a particular justification,
what mathematical properties of compositionality are relevant? This paper
opens with a brief (and inconclusive) argument for the claim that the answer
to the first question is that compositionality is the best available
explanation for the fact that speakers communicate successfully by
means of new sentences, i.e. for the fact that the audience interprets an
utterance as the speaker intended, despite the fact that the sentence used was
new to both of them. The main part of the paper is concerned with what
bearing this claim has on the answer to the second question. What mathematical
properties are relevant for the task of constructing a sentence to be
interpreted in a particular way, and for the task of interpreting that
sentence? For instance, would it be essential, or desirable, that the
homomorphism requirement on the interpretation function be fulfilled?
Some proposed distinctions between kinds of compositionality will be
considered from this perspective.
Theo Janssen, Amsterdam: Frege and the principle of
compositionality
The principle of compositionality is often called Frege's
principle. In this repect it is surprising that in 'Foundations of arithmetic' he
explicitly denies compositionality (never ask for the meaning of a word
in isolotion), an opinion later baptized 'principle of contextuality'.
Several authors (e.g Dummett) have argued that the two principles can
be reconciled, and in fact are two sides of one coin. One may hold
that this reconciliation is successful. In any case semanticists nowadays
propose accounts that have ingredients both of compositionality and of
contextuality.
What I missed in all discussions (e.g. by Dummett) is an investigation
of whether the uttered opinion coincides with Frege's opinion when he
wrote 'Foundations'. Did he indeed mention in 'Foundations' only one side of
the coin, neglecting in that context the other side? There is some
circumstantial evidence that this is not the case. This comes from:
1) Investigations of other (published or unpublished) papers by Frege
from that period . What does he say there about compositionality?
2) Investigations of his scientific correspondence. What does he write
to his colleagues?
3) What do other authors say about these matters?
Finally the direct evidence will be considered:
4) Why does Frege mention his principle in Foundations, where does he
apply it?
As the title indicates, however, the course does not restrict itself to representational issues --- inference is also discussed. In particular, tableaux methods, and their implementation in PROLOG, are introduced. By the end of the course the student will be in a position to write programs which construct representations for non-trivial natural language fragments and perform inference using the output. Moreover, the relevance of the inferential mechanisms introduced to current research in Computational Semantics is discussed in some detail. Our aim is to give relative novices a good overview of the tools currently available to Computational Semanticists --- and an appreciation of their weaknesses.
The course will follow the Gazdar/Kilbury format (ESSLLI 94) of combining background lectures with hands-on lab sessions. The lectures will focus on HPSG, but will conclude with a comparison to other constraint-based grammar formalisms (such as LFG and Extended Categorial Grammar).
The course will target students and researchers who have theoretical knowledge of HPSG or other constraint-based formalisms, but who lack implementational expertise and have an interest in gaining hands-on experience with the implementation of grammar fragments.
Since the course will require an initial learning curve of getting comfortable with the implementational environment, it seems advisable to plan for a two-week course.
Preliminary Schedule
There is no theory of IE -- it is a problem, not an approach. As such, it is a valuable test for any computational linguistic approach which makes claims to being able to deal with significant quantities of real text, and computational techniques from all areas of computational linguistics have been applied with varying degrees of success.
We attempt to explain these convergences by developing a geometrical theory of language structure underlying logical grammar formalism. We connect such geometry of language with geometricisation of proofs in linear logic, and geometry of grammatical dependency. The foundations studied centre on proof nets, not only as originally developed for linear logic, but also for Lambek calculi, POMset logic, and categorial logic and non-commutative linear logic in general. We will examine a range of linguistic applications of proof net syntax, relations to different formalisms, and NLP as proof net construction.
One effect of this is that there is considerable competition for limited space in the fora available for students undertaking their PhDs to report on their progress and results. For the International Natural Language Generation Workshop held in Brighton, UK, in June 1996, 50 papers were submitted but only 18 could be accommodated in the schedule.
The aim of this workshop is to provide a forum for PhD students carrying out research in NLG to present their work. We envisage the workshop taking place over 5 days, using a time slot of approximately 2 hours; these parameters are open to review and dependent upon other scheduling constraints, of course. Our aim would be to select up to 10 students currently working in the area, and have two research presentations per day and extensive time for discussions and debates, potentially choosing specific themes that are currently of particular interest. We would hope to attract a number of established European NLG researchers to ESSLLI, thus providing an excellent forum for current PhD students to receive feedback on the content of their research.
Course prerequisites:
Basic notions of logic; familiarity with KR formalisms such as semantic networks and frames are helpful (but not mandatory)
We recall the most important semantics for logic programs with negation by failure, stable model semantics and well-founded semantics. We then show how these semantics can be extended to include, for instance, classical negation, disjunctions in the head of a rule, and explicit preferences among the rules. The expressiveness of the different languages will be illustrated using various knowledge representation examples.
In the first part, Turing machines are presented in very details and only from these preliminary results, in a very complete, unformal and intuitive way, basic results in classical recursion theory are derived.
In the second part, after performing slight modifications to the standard Turing model, recursion theory on infinite objects (in any concurrency model, infinite objects are infinite computations) is introduced and used to present arithmetical and analytical sets and associated hierarchy results. A closer look to representations of \Pi^1_1-sets (the first level class in the analytical hierarchy) in terms of well-founded orders and well-founded trees, closes this part. This class admits a very natural interpretation in terms of infinitary computations and can be seen as an infinitary analogue to semi-decidable sets.
The final part is devoted to recent applications to concurrency and more particularly to the study of process behaviours (e.g. bisimulation) and process properties (e.g. fairness): expressiveness of concurrency models according to logical complexity of their equivalence verification procedure, completeness of verification methods for termination under fairness, strictness of the modal mu-calculus alternation hierarchy (Mu-calculus is a very general process specification logic e.g. Hennessy-Milner logic and many temporal logics are mu-calculi).
I will give two main applications. First, I will cover the domain of feature structures, and show how feature structures encode partial information. Second, I will show how domain theory provides a natural model theory for the topic of default (non-monotonic) reasoning. Here I will illustrate with a non-monotonic semantics for feature logic, and also a partial model theory and a non-monotonic semantics for first-order logic. This semantics has a lot of conceptual and computational advantages over traditional non-monotonic logics.
Readers may consult the WWW page above for links to papers on the topic.
To develop adequate logical frameworks for this kind of applications, one needs to integrate theories of mental states, action, and agent interaction. Some issues of interest in this area are:
As well, one needs to find representation and reasoning techniques that are appropriate for the target applications, which vary in response-time requirements and opportunities for user intervention. Techniques in use include modal theorem proving, logic programming, model generation approaches, etc. We need better understanding of the range of possible approaches, how they compare, and which are best for various applications.
This symposium will provide a forum for researchers in this area to compare their approaches and discuss ways of addressing issues of interest.