Trace-Based Abstract Interpretation of Operational Semantics

We present trace-based abstract interpretation, a unification of severallines of research on applying Cousot-Cousot-style abstract interpretation a.i. tooperational semantics definitions (such as flowchart, big-step, and small-step semantics)that express a programs semantics as a concrete computation tree of trace paths. Aprograms trace-based a.i. is also a computation tree whose nodes contain abstractions ofstate and whose paths simulate the paths in the programs concrete computation tree.Using such computation trees, we provide a simple explanation of the central concept of collecting semantics, and we distinguish concrete from abstract collectingsemantics and state-based from path-based collecting semantics. We also expose therelationship between collecting semantics extraction and results garnered from flow-analytic and model-checking-based analysis techniques. We adapt concepts fromconcurrency theory to formalize safe and live a.i.s for computation trees; in particular, coinduction techniques help extend fundamental results to infinite computation trees.Problems specific to the various operational semantics methodologies are discussed: Big-step semantics cannot express divergence, so we employ a mixture of induction andcoinduction in response; small-step semantics generate sequences of programconfigurations unbounded in size, so we abstractly interpret source language syntax.Applications of trace-based a.i. to data-flow analysis, model checking, closure analysis,and concurrency theory are demonstrated.     

Dualities between alternative semantics for logic programming and nonmonotonic reasoning

The Gelfond-Lifschitz operator associated with a logic program (and likewise the operator associated with default theories by Reiter) exhibits oscillating behavior. In the case of logic programs, there is always at least one finite, nonempty collection of Herbrand interpretations around which the Gelfond-Lifschitz operator bounces around. The same phenomenon occurs with default logic when Reiter's operator is considered. Based on this, a stable class semantics and extension class semantics has been proposed. The main advantage of this semantics was that it was defined for all logic programs (and default theories), and that this definition was modelled using the standard operators existing in the literature such as Reiter's operator. In this paper our primary aim is to prove that there is a very interestingduality between stable class theory and the well-founded semantics for logic programming. In the stable class semantics, classes that were minimal with respect to Smyth's power-domain ordering were selected. We show that the well-founded semantics precisely corresponds to a class that is minimal w.r.t. Hoare's power domain ordering: the well-known dual of Smyth's ordering. Besides this elegant duality, this immediately suggests how to define a well-founded semantics for default logic in such a way that the dualities that hold for logic programming continue to hold for default theories. We show how the same technique may be applied to strong autoepistemic logic: the logic of strong expansions proposed by Marek and Truszczynski.     

Dynamic interpretation and hoare deduction

In this paper we present a dynamic assignment language which extends the dynamic predicate logic of Groenendijk and Stokhof [1991: 39–100] with assignment and with generalized quantifiers. The use of this dynamic assignment language for natural language analysis, along the lines of o.c. and [Barwise, 1987: 1–29], is demonstrated by examples. We show that our representation language permits us to treat a wide variety of donkey sentences: conditionals with a donkey pronoun in their consequent and quantified sentences with donkey pronouns anywhere in the scope of the quantifier. It is also demonstrated that our account does not suffer from the so-called proportion problem.Discussions about the correctness or incorrectness of proposals for dynamic interpretation of language have been hampered in the past by the difficulty of seeing through the ramifications of the dynamic semantic clauses (phrased in terms of input-output behaviour) in non-trivial cases. To remedy this, we supplement the dynamic semantics of our representation language with an axiom system in the style of Hoare. While the representation languages of barwise and Groenendijk and Stokhof were not axiomatized, the rules we propose form a deduction system for the dynamic assignment language which is proved correct and complete with respect to the semantics.Finally, we define the static meaning of a program of the dynamic assignment language as the weakest condition such that terminates successfully on all states satisfying , and we show that our calculus gives a straightforward method for finding static meanings of the programs of the representation language.     

Semantic analysis in XTRA,an English — Chinese machine translation system

This paper concerns the resolution of lexical ambiguity in a machine translation environment. We describe the integration of principles of selection restrictions. Preference Semantics, and intelligent relaxation of constraints in handling lexical ambiguity. The approach differs from many previous MT systems in that it is more powerful than brute force systems, while more realistic than systems that assume a large degree of coded encyclopedia information for full understanding.     

Computing with Contexts

We investigate a representation of contexts, expressions with holes in them, that enables them to be meaningfully transformed, in particular -converted and -reduced. In particular we generalize the set of -expressions to include holes, and on these generalized entities define -reduction (i.e., substitution) and filling so that these operations preserve -congruence and commute. The theory is then applied to allow the encoding of reduction systems and operational semantics of call-by-value calculi enriched with control, imperative and concurrent features.     

Explanation-based interpretation of open-textured concepts in logical models of legislation

In this paper we discuss a view of the Machine Learning technique called Explanation-Based Learning (EBL) or Explanation-Based Generalization (EBG) as a process for the interpretation of vague concepts in logic-based models of law.The open-textured nature of legal terms is a well-known open problem in the building of knowledge-based legal systems. EBG is a technique which creates generalizations of given examples on the basis of background domain knowledge. We relate these two topics by considering EBG's domain knowledge as corresponding to statute law rules, and EBG's training example as corresponding to a precedent case.By making the interpretation of vague predicates as guided by precedent cases, we use EBG as an effective process capable of creating a link between predicates appearing as open-textured concepts in law rules, and predicates appearing as ordinary language wording for stating the facts of a case.Standard EBG algorithms do not change the deductive closure of the domain theory. In the legal context, this is only adequate when concepts vaguely defined in some law rules can be reformulated in terms of other concepts more precisely defined in other rules. We call theory reformulation the process adopted in this situation of complete knowledge.In many cases, however, statutory law leaves some concepts completely undefined. We then propose extensions to the EBG standard that deal with this situation of incomplete knowledge, and call theory revision the extended process. In order to fill in knowledge gaps we consider precedent cases supplemented by additional heuristic information. The extensions proposed treat heuristics represented by abstraction hierarchies with constraints and exceptions.In the paper we also precisely characterize the distinction between theory reformulation and theory revision by stating formal definitions and results, in the context of the Logic Programming theory.We offer this proposal as a possible contribution to cross fertilization between machine learning and legal reasoning methods.     

The “explicit-implicit” distinction

Much of traditional AI exemplifies the explicit representation paradigm, and during the late 1980's a heated debate arose between the classical and connectionist camps as to whether beliefs and rules receive an explicit or implicit representation in human cognition. In a recent paper, Kirsh (1990) questions the coherence of the fundamental distinction underlying this debate. He argues that our basic intuitions concerning explicit and implicit representations are not only confused but inconsistent. Ultimately, Kirsh proposes a new formulation of the distinction, based upon the criterion ofconstant time processing.The present paper examines Kirsh's claims. It is argued that Kirsh fails to demonstrate that our usage of explicit and implicit is seriously confused or inconsistent. Furthermore, it is argued that Kirsh's new formulation of the explicit-implicit distinction is excessively stringent, in that it banishes virtually all sentences of natural language from the realm of explicit representation. By contrast, the present paper proposes definitions for explicit and implicit which preserve most of our strong intuitions concerning straightforward uses of these terms. It is also argued that the distinction delineated here sustains the meaningfulness of the abovementioned debate between classicists and connectionists.     

Information Gaps as Communication Needs: A New Semantic Foundation for Some Non-Classical Logics

Semantics connected to some information based metaphor are well-known in logic literature: a paradigmatic example is Kripke semantic for Intuitionistic Logic. In this paper we start from the concrete problem of providing suitable logic-algebraic models for the calculus of attribute dependencies in Formal Contexts with information gaps and we obtain an intuitive model based on the notion of passage of information showing that Kleene algebras, semi-simple Nelson algebras, three-valued ukasiewicz algebras and Post algebras of order three are, in a sense, naturally and directly connected to partially defined information systems. In this way wecan provide for these logic-algebraic structures a raison dêetre different from the original motivations concerning, for instance, computability theory.     

Symbols and Computation A Critique of the Computational Theory of Mind

Over the past several decades, the philosophical community has witnessed the emergence of an important new paradigm for understanding the mind.¹ The paradigm is that of machine computation, and its influence has been felt not only in philosophy, but also in all of the empirical disciplines devoted to the study of cognition. Of the several strategies for applying the resources provided by computer and cognitive science to the philosophy of mind, the one that has gained the most attention from philosophers has been the Computational Theory of Mind (CTM). CTM was first articulated by Hilary Putnam (1960, 1961), but finds perhaps its most consistent and enduring advocate in Jerry Fodor (1975, 1980, 1981, 1987, 1990, 1994). It is this theory, and not any broader interpretations of what it would be for the mind to be a computer, that I wish to address in this paper. What I shall argue here is that the notion of symbolic representation employed by CTM is fundamentally unsuited to providing an explanation of the intentionality of mental states (a major goal of CTM), and that this result undercuts a second major goal of CTM, sometimes refered to as the vindication of intentional psychology. This line of argument is related to the discussions of derived intentionality by Searle (1980, 1983, 1984) and Sayre (1986, 1987). But whereas those discussions seem to be concerned with the causal dependence of familiar sorts of symbolic representation upon meaning-bestowing acts, my claim is rather that there is not one but several notions of meaning to be had, and that the notions that are applicable to symbols are conceptually dependent upon the notion that is applicable to mental states in the fashion that Aristotle refered to as paronymy. That is, an analysis of the notions of meaning applicable to symbols reveals that they contain presuppositions about meaningful mental states, much as Aristotle's analysis of the sense of healthy that is applied to foods reveals that it means conducive to having a healthy body, and hence any attempt to explain mental semantics in terms of the semantics of symbols is doomed to circularity and regress. I shall argue, however, that this does not have the consequence that computationalism is bankrupt as a paradigm for cognitive science, as it is possible to reconstruct CTM in a fashion that avoids these difficulties and makes it a viable research framework for psychology, albeit at the cost of losing its claims to explain intentionality and to vindicate intentional psychology. I have argued elsewhere (Horst, 1996) that local special sciences such as psychology do not require vindication in the form of demonstrating their reducibility to more fundamental theories, and hence failure to make good on these philosophical promises need not compromise the broad range of work in empirical cognitive science motivated by the computer paradigm in ways that do not depend on these problematic treatments of symbols.     

A logical encoding of the π-calculus: model checking mobile processes using tabled resolution

We present MMC, a model checker for mobile systems specified in the style of the -calculus. MMCs development builds on that of XMC, a model checker for an expressive extension of Milners value-passing calculus implemented using the XSB tabled logic-programming engine. MMC addresses the salient issues that arise in the -calculus, including scope extrusion and intrusion and dynamic generation of new names to avoid name capture. We show that logic programming provides an efficient implementation platform for model checking -calculus specifications and can be used to obtain an exact encoding of the -calculuss transitional semantics. Moreover, MMC is easily extended to handle process expressions in the spi-calculus of Abadi and Gordon. Our experimental data show that MMC outperforms other known tools for model checking the -calculus.     

Why isn't my pocket calculator a thinking thing?

Conclusion What the preceding arguments show — I take it — is that none of the four traditional marks of the mental considered provide a supportable basis for denying that Cal calculates in the same sense as you or I; i.e., I have sought to show that our initial syllogism does not commit the fallacy of four terms by equivocating on calculates, its middle. I will conclude by remarking why the argument — at least as I intend it, and on its least tendentious reading — doesn't equivocate on its major, thinks, either. Ordinarily think is a generic term for any of several different mental activities or states. According to Descartes, a thing that thinks is a thing which doubts, understands, affirms, denies, is willing, is unwilling, and also imagines and has sensory perceptions (1642: 19). Similarly, my dictionary (Webster's New Collegiate), under think, mentions conceive, judge, consider, surmise, expect, determine, resolve, reason, intend, purpose, reflect, infer, opine, and decide. In this ordinary generic sense of the term, I take it, it's undeniable that calculating is thinking, and — if my arguments are sound — that my pocket calculator calculates and consequently thinks.Perhaps some special sense of thinking can be made out for which calculating is not sufficient — perhaps some sense in which it's not sufficient to doubtor understandor will, etc., but in which it's necessary to (be able to) doubtand understandand will, etc. (as Descartes surely intended). Perhaps there is some sense in which thinking requires such unity, or universality of mental capacity — or alternatively some other traditional (or perhaps some non-traditional) mark(s) of the mental. At any rate — whether or not such a sense of thought can be made out — I have only claimed that Cal thinks in the ordinary generic sense of being a subject of at least one kind of contentful or mental state, not that he is a unified, or conscious, or autonomous self or soul or thinker in some special proprietary philosophical sense. I leave it to the opponent of AI to clarify what this sense is and to make out the case, if it can be made, against Cal's thinking inthis sense.     

A New Implementation of Automath

This paper presents aut, a modern Automath checker. It is a straightforward re-implementation of the Zandleven Automath checker from the seventies. It was implemented about five years ago, in the programming language C. It accepts both the AUT-68 and AUT-QE dialects of Automath. This program was written to restore a damaged version of Jutting's translation of Landau's Grundlagen. Some notable features: It is fast. On a 1 GHz machine it will check the full Jutting formalization (736 K of nonwhitespace Automath source) in 0.6 seconds. Its implementation of -terms does not use named variables or de Bruijn indices (the two common approaches) but instead uses a graph representation. In this representation variables are represented by pointers to a binder. The program can compile an Automath text into one big Automath single line-style -term. It outputs such a term using de Bruijn indices. (These -terms cannot be checked by modern systems like Coq or Agda, because the -typed -calculi of de Bruijn are different from the -typed -calculi of modern type theory.)The source of aut is freely available on the Web at the address .     

A Mathematical Analysis of Pānini’s <Emphasis Type="Italic">Śivasūtras</Emphasis>

In Pninis grammar of Sanskrit one finds the ivastras, a table which defines the natural classes of phonological segments in Sanskrit by intervals. We present a formal argument which shows that, using his representation method, Pninis way of ordering the phonological segments to represent the natural classes is optimal. The argument is based on a strictly set-theoretical point of view depending only on the set of natural classes and does not explicitly take into account the phonological features of the segments, which are, however, implicitly given in the way a language clusters its phonological inventory. The key idea is to link the graph of the Hasse-diagram of the set of natural classes closed under intersection to ivastra-style representations of the classes. Moreover, the argument is so general that it allows one to decide for each set of sets whether it can be represented with Pninis method. Actually, Pnini had to modify the set of natural classes to define it by the ivastras (the segment h plays a special role). We show that this modification was necessary and, in fact, the best possible modification. We discuss how every set of classes can be modified in such a way that it can be defined in a ivastra-style representation.¹     

Comparative complexity of the representation of languages by probabilistic automata

We analyze the effect of the degree of isolation of a cut point on the number of states P(U, ) of a probabilistic automaton representing the language U. We give an example of a language Uⁿ consisting of words of length n such that there exist numbers < for which P(Uⁿ, )/P(Uⁿ, )0 as n.Translated from Kibernetika, No. 3, pp. 21–25, May–June, 1989.     

Coordinating Multiple Agents via Reinforcement Learning

In this paper, we attempt to use reinforcement learning techniques to solve agent coordination problems in task-oriented environments. The Fuzzy Subjective Task Structure model (FSTS) is presented to model the general agent coordination. We show that an agent coordination problem modeled in FSTS is a Decision-Theoretic Planning (DTP) problem, to which reinforcement learning can be applied. Two learning algorithms, coarse-grained and fine-grained, are proposed to address agents coordination behavior at two different levels. The coarse-grained algorithm operates at one level and tackle hard system constraints, and the fine-grained at another level and for soft constraints. We argue that it is important to explicitly model and explore coordination-specific (particularly system constraints) information, which underpins the two algorithms and attributes to the effectiveness of the algorithms. The algorithms are formally proved to converge and experimentally shown to be effective.     

Definability of Polyadic Lifts of Generalized Quantifiers

We study generalized quantifiers on finite structures.With every function : we associate a quantifier Q by letting Q x say there are at least (n) elementsx satisfying , where n is the sizeof the universe. This is the general form ofwhat is known as a monotone quantifier of type < 1 >.We study so called polyadic liftsof such quantifiers. The particular lifts we considerare Ramseyfication, branching and resumption.In each case we get exact criteria fordefinability of the lift in terms of simpler quantifiers.     

Representing and using legal knowledge in integrated decision support systems: DataLex WorkStations

There is more to legal knowledge representation than knowledge-bases. It is valuable to look at legal knowledge representation and its implementation across the entire domain of computerisation of law, rather than focussing on sub-domains such as legal expert systems. The DataLex WorkStation software and applications developed using it are used to provide examples. Effective integration of inferencing, hypertext and text retrieval can overcome some of the limitations of these current paradigms of legal computerisation which are apparent when they are used on a stand-alone basis. Effective integration of inferencing systems is facilitated by use of a (quasi) natural language knowledge representation, and the benefits of isomorphism are enhanced. These advantages of integration apply to all forms of inferencing, including document generation and casebased inferencing. Some principles for development of integrated legal decision support systems are proposed.     

A treatment of plurals and plural quantifications based on a theory of collections

Collective entities and collective relations play an important role in natural language. In order to capture the full meaning of sentences like The Beatles sing Yesterday, a knowledge representation language should be able to express and reason about plural entities — like the Beatles — and their relationships — like sing — with any possible reading (cumulative, distributive or collective).In this paper a way of including collections and collective relations within a concept language, chosen as the formalism for representing the semantics of sentences, is presented. A twofold extension of theA–C concept language is investigated: (1) special relations introduce collective entities either out of their components or out of other collective entities, (2) plural quantifiers on collective relations specify their possible reading. The formal syntax and semantics of the concept language is given, together with a sound and complete algorithm to compute satisfiability and subsumption of concepts, and to compute recognition of individuals.An advantage of this formalism is the possibility of reasoning and stepwise refining in the presence of scoping ambiguities. Moreover, many phenomena covered by the Generalized Quantifiers Theory are easily captured within this framework. In the final part a way to include a theory of parts (mereology) is suggested, allowing for a lattice-theoretical approach to the treatment of plurals.     

Behaviour Synthesis of the Erect Stance for a Biped Control

In this paper we use free fall approach to develop a high level control/command strategy for a bipedal robot called BIPMAN, based on a multi-chain mechanical model with a general control architecture. The strategy is composed of three levels: the Legs and arms level, the Coordinator level and the Supervisor level. The Coordinator level is devoted to controlling leg movements and to ensure the stability of the whole biped. Actually perturbation effects threaten the equilibrium of the human robot and can only be compensated using a dynamic control strategy. This one is based on dynamic stability studies with a center of mass acceleration control and a force distribution on each leg and arm. Free fall in the gravity field is assumed to be deeply involved in the human locomotor control. According to studies of this specific motion through a direct dynamic model,the notion of equilibrium classes is introduced. They allow one to define time intervals in which the biped is able to maintain its posture. This notion is used for the definition of a reconfigurable high level control of the robot.     

Sequential method in propositional dynamic logic

Summary Recently prepositional modal logic of programs, called prepositional dynamic logic, has been developed by many authors, following the ideas of Fisher and Ladner [1] and Pratt [12]. The main purpose of this paper is to present a Gentzen-type sequential formulation of this logic and to establish its semantical completeness with due regard to sequential formulation as such. In a sense our sequential formulation might be regarded as a powerful tool to establish the completeness theorem of already familiar axiomatizations of prepositional dynamic logic such as seen in Harel [4], Parikh [11] or Segerberg [15]. Indeed our method is powerful enough in completeness proof to yield a desired structure directly without making a detour through such intermediate constructs as a pseudomodel or a nonstandard structure, which can be seen in Parikh [11]. We also show that our sequential system of prepositional dynamic logic does not enjoy the so-called cut-elimination theorem.