bluuebunny/crossref_metadata_2025 huggingface dataset:
Synthesizing plans that contain actions with context‐dependent effects1
Authors: Pednault Edwin P. D.
Published: April 2007

This paper presents a method of solving planning problems that involve actions whose effects change according to the situations in which they are performed. The approach is an extension of the conventional planning methodology in which plans are constructed through an iterative process of scanning for goals that are not yet satisfied, inserting actions to achieve them, and introducing subgoals to these actions. This methodology was originally developed under the assumption that one would be dealing exclusively with actions that produce the same effects in every situation. The extension involves introducing additional subgoals to actions above and beyond the preconditions of execution normally introduced. These additional subgoals, called secondary preconditions, ensure that the actions are performed in contexts conducive to producing the effects we desire. This paper defines and analyzes secondary preconditions from a mathematically rigorous standpoint and demonstrates how they can be derived from regression operators.
Instance‐based prediction of real‐valued attributes
Authors: Kibler Dennis , Aha David W. , Albert Marc K.
Published: April 2007

Instance‐based representations have been applied to numerous classification tasks with some success. Most of these applications involved predicting a symbolic class based on observed attributes. This paper presents an instance‐based method for predicting a numeric value based on observed attributes. We prove that, given enough instances, if the numeric values are generated by continuous functions with bounded slope, then the predicted values are accurate approximations of the actual values. We demonstrate the utility of this approach by comparing it with a standard approach for value prediction. The instance‐based approach requires neither ad hoc parameters nor background knowledge.
Curved Mondrians: shading analysis of patterned objects1
Authors: Bischof Walter F. , Ferraro Mario
Published: April 2007

Most shape‐from‐shading methods assume that surface reflectance is constant within large image regions. This assumption is violated in natural scenes with objects made from different materials. We present a more general method for recovering shape from shading, assuming that surfaces are smooth and albedo is piecewise constant, as would be the case if a Mondrian image was painted on a smooth curved surface. Our method is based on combining Brooks and Horn's method for shape recovery with the recovery of albedo using stochastic relaxation.
Expressing unrestricted grammars by extended definite clause grammars1
Authors: Knudsen Erik
Published: April 2007

A definition of extended definite clause grammars and their relationship to unrestricted grammars are presented. A method for translating extended definite clause grammars describing unrestricted grammars into executable prolog programs is given. Three different parsing techniques are presented, and for each a complete presentation of how to incorporate unrestricted grammars in the actual formalism is done. Extended definite clause grammar is a powerful formalism usable for specifying grammars in natural language processing systems.
Likelihood, probability, and knowledge1
Authors: Halpern Joseph Y. , McAllester David A.
Published: April 2007

The modal logic LL was introduced by Halpern and Rabin as a means of doing qualitative reasoning about likelihood. Here the relationship between LL and probability theory is examined. It is shown that there is a way of translating probability assertions into LL in a sound manner, so that LL in some sense can capture the probabilistic interpretation of likelihood. However, the translation is subtle; several more obvious attempts are shown to lead to inconsistencies. We also extend LL by adding modal operators for knowledge. This allows us to reason about the interaction between knowledge and likelihood. The propositional version of the resulting logic LLK is shown to have a complete axiomatization and to be decidable in exponential time, provably the best possible.
Formalizing planning knowledge for hierarchical planning
Authors: Yang Qiang
Published: April 2007

A hierarchical planning system achieves efficiency by planning with the most important conditions first, and considering details later in the planning process. Few attempts have been made to formalize the structure of the planning knowledge for hierarchical planning. For a given domain, there is usually more than one way to define its planning knowledge. Some of the definitions can lead to efficient planning, while others may not. In this paper, we provide a set of restrictions which defines the relationships between a non‐primitive action and its set of subactions. When satisfied, these restrictions guarantee improved efficiency for hierarchical planning. One important feature of these restrictions is that they are syntactic and therefore do not depend on the particular structure of any plan. Along with these restrictions, we also provide algorithms for preprocessing the planning knowledge of a hierarchical planner. When used during planning, the preprocessed operator hierarchies can enable a planner to significantly reduce its search space.
Building geometric world models with graph synthesis for sensor fusion in mobile robots1
Authors: Lang Sherman Y. T. , Wong Andrew K. C.
Published: April 2007

This paper presents a description of the application of an attributed graph based approach to the synthesis of a geometric world model for use in navigation by a mobile robot. Our aim is to develop the theoretical aspects of graph synthesis for mobile robot world knowledge acquisition, and to demonstrate the validity of the approach with a simulation before implementation on the rover. A boundary representation of free space consisting of directed line segments organized into a directed attributed graph is used. The synthesis problem can be considered as having two parts: matching of a local model with a global model and the construction of a new global model. Structural and geometric local and global constraints are used to limit and direct the search for valid graph mappings. The constraints are the source of rules for matching primitives and graphs and are used in the process of constructing a new world model graph. An algorithm for graph synthesis is implemented in a software simulation for testing and experimentation.
Denkprothesen: on programs that reason
Authors: DWYER MICHAEL W.
Published: April 2007

This paper considers computer programs that purport to do inference. It finds the essence of their reasoning ability to reside in a particular relationship which exists between the computations described by the texts of those programs and machine‐independent formal representations of the theories in which they are said to reason. The principal novelties in the treatment of this question are the use of explicit “abstraction functions” between states of a computation and sets of sentences of a theory, and the notion of global “inference relations” which characterize the set of all inferences of which a system is capable. The central result of the paper is an “arrow‐theoretic” characterization of the concept of a knowledge representation, along with the related concept of a knowledge representation realization. The notions of equivalence and subsumption for knowledge representations are defined, as well as equivalence of knowledge representation realizations. Finally, important issues of expression evaluation and control are addressed. The paper concludes with a slogan: “The AI is in the arrows.”

Cet article traite des programmes informatiques qui prétendent faire de ľinférence. Ľauteur constate que ľessentiel de leur capacityé de raisonnement réside dans la relation particulière qui existe entre les calculs décrits par les textes de ces programmes et les représentations formelles non liées à un type de machine des théories dans le cadre desquelles ils sont supposés raisonner. Les principales nouveautés dans le traitement de cette question sont ľutilisation de fonctions ?abstraction explicites éntre les etats ?un calcul et les ensembles de phrases ?une théorie, et la notion de relations ?inférence globales qui caractérisent ľensemble de toutes les inférences dont un système est capable. Le principal résultat de cet article est une caractérisation du concept de la représentation des connaissances, ainsi que du concept connexe de la réalisation de la représentation des connaissances. Les notions ?équivalence et de sous‐somption pour la représentation des connaissances sont définies, ainsi que ľéquivalence des réalisations de la représentation des connaissances. Enfin, des questions importantes comme ľanalyse et le contrǒle ?expressions sont traitées.
Notes on Ginsberg's multivalued logics
Authors: SCHAERF MARCO
Published: April 2007

The use of multivalued logics for knowledge representation and nonmonotonic reasoning has often been advocated, in particular within the general framework proposed by Ginsberg in his paper “Multivalued logics: a uniform approach to reasoning in artificial intelligence.” His system is based on a multivalued logic with an arbitrary number of truth values classified with respect to two partial orders, a truth order and a knowledge order. This classification is very interesting and gives an intuitive appeal to the framework. In this paper the work by Ginsberg is critically reviewed, pointing out some flaws and ways to overcome them. Moreover, we present some ideas on how to modify the original schema in order to obtain a more semantically well‐founded framework.

L'utilisation de la Iogique multivalente pour la représentation des connaissances et le raisonnement non monotone a souvent été préconisée, en particulier à l'intérieur du cadre général proposé par Ginsberg dans son article intitulé? Multivalued logics: a uniform approach to reasoning in artificial intelligence ? Son système est basé sur une logique multivalente comportant un nombre arbitraire de valeurs de vérité classées selon deux ordres partiels: un ordre de vérité et un ordre de connaissances. Cette classification est très intéressante et donne un attrait intuitif au cadre. Dans cet article, l'auteur examine le travail de Ginsberg, y relève des lacunes et propose des moyens de les corriger. De plus, il expose certaines idées en vue de modifier le schéma original et ainsi obtenir un meilleur cadre du point de vue de la sémantique.
Self‐learning inductive inference machines
Authors: CERANS KARLIS H. , SMITH CARL H.
Published: April 2007

Self‐knowledge is a concept that is present in several philosophies. In this article, we consider the issue of whether or not a learning algorithm can in some sense possess self‐knowledge. The question is answered affirmatively. Self‐learning inductive inference algorithms are taken to be those that learn programs for their own algorithms, in addition to other functions.

La connaissance de soi est un concept qui se retrouve dans plusieurs philosophies. Dans cet article, les auteurs s'interrogent à savoir si un algorithme d' apprentissage peut dans une certaine mesure posséder la connaissance de soi. lis apportent une reponse positive a cette question. Les algorithmes d'inference inductive autodidactes sont ceux qui font l'apprentissage de programmes pour leurs propres algorithmes, en plus d' autres fonctions.
Planning in polynomial time: the SAS‐PUBS class
Authors: BÄCKSTRÖM CHRISTER , KLEIN INGER
Published: April 2007

This article describes a polynomial‐time, O(n3), planning algorithm for a limited class of planning problems. Compared to previous work on complexity of algorithms for knowledge‐based or logic‐based planning, our algorithm achieves computational tractability, but at the expense of only applying to a significantly more limited class of problems. Our algorithm is proven correct, and it always returns a parallel minimal plan if there is a plan at all.

Cet article décrit un algorithme de planification de temps polynomial O(n3) pour une classe restreinte de problemes de planification. Contrairement aux travaux précédents sur la complexité des algorithmes pour la planification basée sur la logique ou les connaissances, l' algorithme dont il est question dans cet article permet d' obtenir la tractabilityé computationnelle; cependant, il ne peut ětre appliqué qu'à une catégorie beaucoup plus restreinte de problèmes. Cet algorithme s'est done révélé correct et il génère toujours un plan minimal en parallèle lorsqu'il y en a un.
A new model of lexical choice for nouns1
Authors: Reiter Ehud
Published: April 2007

Natural language generation systems should choose nouns by searching for lexical units that (i) are known to the user; (ii) truthfully describe the object being lexicalised; (iii) convey sufficient information to fulfill the system's underlying communicative goals; and (iv) are maximal under a lexical preference function. This model of lexical choice allows a clean separation to be made between what the system knows about the object being lexicalized and what it wishes to communicate about this object. The model also allows lexical choice to be biased towards basic‐level and other preferred lexical units.

Les systèmes de génération du langage naturel devraient choisir des noms en recherchant des unités lexicales (i) qui soient connues de ľutilisateur, (ii) qui décrivent fidèlement ľobjet soumis à un traitement lexical, (iii) qui transmettent suffisamment ?information pour répondre aux objectifs de communication du système, et (iv) qui soient maximales dans une fonction de préférence lexicale. Ce modéle de choix lexical permet une nette séparation entre ce que le système sait à propos de ľobjet soumis à un traitement lexical et ce qu'il souhaite communiquer à propos de cet objet. Le modèle permet également au choix lexical ?avoir un préjugé vis‐à‐vis les unités lexicales de niveau de base et autres unités lexicales préférées.
TOWARD A THEORY OF COMPILATION FOR NATURAL LANGUAGE GENERATION
Authors: Patten Terry , Geis Michael L. , Becker Barbara D.
Published: April 2007

This article proposes a framework in which knowledge compilation can be exploited in a principled manner for the task of generating natural language. We have constructed an utterance generator for one side of a realistic dialogue that exploits compiled knowledge of, for instance, the effects of discourse pragmatics on text plans, and the effects of register, style, and politeness on text realization. The motivation for this work is the significant impact that compiled knowledge has on the speed of language generation.
IDIOMS, NON‐LITERAL LANGUAGE AND KNOWLEDGE REPRESENTATION1
Authors: van der Linden Erik‐Jan
Published: April 2007

There are two pertinent themes in the study of idioms in the area of natural language processing. Firstly, idioms should be defined and located in the space of non‐literal expressions. This will be the first aim of this paper. Secondly, a processing model should be developed. In this paper, the application of knowledge representation techniques in three different models for the representation and processing of idioms are discussed. The first, a symbolic procedural model extends the two‐level model which was originally developed in computational morphology. The second is a simple localist connectionist model. The third, a symbolic hierarchical model, represents idioms as part of a lexicon conceived as an inheritance hierarchy. A comparison between the models is made in which the focus lies on the resolution of the ambiguity of idioms, the relation between the literal and non‐literal interpretation and the syntactic flexibility of idiomatic expressions.
BELIEF IN METAPHOR: TAKING COMMONSENSE PSYCHOLOGY SERIOUSLY1
Authors: Barnden John A.
Published: April 2007

Evidence from real discourse suggests that beliefs and other mental states (propositional attitudes) are often viewed by speakers and other agents in a metaphorical way. Typical metaphors are MIND‐AS‐CONTAINER—the view of the mind as a container, with thoughts being physical objects inside it—or IDEAS‐AS‐INTERNAL‐UTTERANCES—the view of thoughts as natural language utterances inside an agent's head. It is therefore necessary for AI systems for mental‐state representation/reasoning to reason within such views. This approach contrasts with the highly abstract logical stance adopted in most propositional attitude research. A formal representation scheme based on the various metaphors has been partially developed. In this paper, it is mainly the MIND‐AS‐CONTAINER segment of the formal representation scheme that is detailed. Inference processes operating over the scheme are also presented. The crucial distinguishing feature of the representation scheme is that the description of mental states is directly based on physical predicates, objects and so on, as opposed to abstract, tailor‐made, mental ones. That is, the representation scheme is itself explicitly metaphor‐imbued.
ON THE SEMANTICS OF STABLE INHERITANCE REASONING
Authors: Boutilier Craig
Published: April 2007

Inheritance reasoners have traditionally been viewed as argument systems, or algorithms that determine reasonable conclusions by constructing acceptable arguments. While the intended meaning of links in such networks is understood, formal semantic accounts are troublesome, as are semantic accounts of the inference process. We adopt a different perspective, suggesting that links be interpreted as conditional sentences with appropriate truth conditions rather than uninterpreted “reasons.” The conditional logic CT4D is used for this purpose. Furthermore, we characterize inference in our networks in terms of preferred (or minimal) models. In the process, we identify some key differences between our account of inference and those based on the notion of inferential distance, specifically with respect to the stability of reasoning. Key words: nonmonotonic reasoning, inheritance hierarchies, minimal models, conditional logic.
FROM PLAN CRITIQUING TO CLARIFICATION DIALOGUE FOR COOPERATIVE RESPONSE GENERATION*
Authors: VAN BEEK PETER , COHEN ROBIN , SCHMIDT KEN
Published: April 2007

Recognizing the plan underlying a query aids in the generation of an appropriate response. In this paper, we address the problem of how to generate cooperative responses when the user's plan is ambiguous. We show that it is not always necessary to resolve the ambiguity, and provide a procedure that estimates whether the ambiguity matters to the task of formulating a response. The procedure makes use of the critiquing of possible plans and identifies plans with the same fault. We illustrate the process of critiquing with examples. If the ambiguity does matter, we propose to resolve the ambiguity by entering into a clarification dialogue with the user and provide a procedure that performs this task. Together, these procedures allow a question‐answering system to take advantage of the interactive and collaborative nature of dialogue in order to recognize plans and resolve ambiguity. This work therefore presents a view of generation in advice‐giving contexts which is different from the straightforward model of a passive selection of responses to questions asked by users. We also report on a trial implementation in a course‐advising domain, which provides insights on the practicality of the procedures and directions for future research.
THE LazyRMS: AVOIDING WORK IN THE ATMS
Authors: Kelleher Gerry , van der Gaag Linda
Published: April 2007

The basic algorithms involved in reason maintenance in the standard ATMS is known to have a computational complexity that is exponential in the worst case. Yet, also in average‐case problem solving, the ATMS often lays claim to a major part of the computational effort spent by a problem solver/ATMS system. In this paper, we argue that within the limits of the worst‐case computational complexity, it is possible to improve on the average‐case complexity of reason maintenance and query processing by eliminating computation that is of no relevance to the problem solver's performance. To this purpose, we present a set of algorithms designed to control the effort spent by the ATMS on label updating. The basic idea underlying these algorithms is that of lazy evaluation: labels are not automatically maintained on all datums but are computed only when needed (either directly or indirectly) by the problem solver. The algorithms have been implemented in the LazyRMS with which we have experimented in the context of model‐based diagnosis; our experiments show a substantial saving in the computational effort spent on reason maintenance.
WORD ORDER VARIATION AND TREE‐ADJOINING GRAMMAR
Authors: Rambow Owen , Lee Young‐Suk
Published: April 2007

In many head‐final languages such as German, Hindi, Japanese, and Korean, but also in some other languages such as Russian, arguments of a verb can occur in any order. Furthermore, arguments can occur outside of their clause (“long‐distance scrambling”). Long‐distance scrambling presents a challenge both to linguistic theory and to formal frameworks for linguistic description because it is very unconstrained: in a given sentence, there is no bound on the number of elements that can be scrambled nor on the distance over which each element can scramble. We discuss two formal frameworks related to tree‐adjoining grammar. First, we show how scrambling facts from Korean can be handled by nonlocal multicomponent TAG (MC‐TAG). Then, we argue that overt vWt‐movement in German makes this analysis unattractive, and suggest a new version of MC‐TAG, called V‐TAG, which can handle both Korean and German word order variation. Interestingly, this new version has more attractive computational properties than nonlocal MC‐TAG. We conclude that this formalism is an attractive basis for the development of psycholinguistic processing models and practical parsers alike.
A NEW AUTOMATON MODEL FOR TAGS: 2‐SA
Authors: Becker Tilman
Published: April 2007

In this paper, we introduce and define a new class of automata (pushdown automata with n stacks, abbreviated as n‐SA). The ultimate aim is to give a new characterization of LCRFL, the class of languages accepted by a linear context‐free rewriting system (LCFRS). In particular, we introduce 2‐SA as a new automaton model for tree‐adjoining grammars (TAG). In the simplest cases (0‐SA and 1‐SA), the languages that are accepted by the automata are the regular and context‐free languages respectively. A more complex case is the case of a 2‐SA which accepts TALs. The n‐SA creates an infinite hierarchy of languages and it seems that this hierarchy corresponds to others in the class LCFRL. The 2‐SA corresponds closely to the EPDA (embedded pushdown automaton, an automaton model equivalent to TAGs). Unlike the EPDA, which allows push operations “below the top stack,” an n‐SA allows push and pop operations only on the top of their (multiple) stacks. So n‐SA trade simpler operations against an also simpler but expanded storage structure.
NOMINAL STRUCTURES AND STRUCTURAL RECURSION
Authors: Frank Robert , Kroch Anthony
Published: April 2007

It is possible within tree‐adjoining grammar to reproduce many of the syntactic analyses originally formulated by linguists in transformational terms. To the extent that these analyses are well motivated empirically, this fact makes TAG interesting for use in developing computational learning and processing models (Joshi 1990; Frank 1992; Rambow 1994), since the use of other nontransformational formalisms sometimes forces choices of linguistic description different from those ordinarily made by descriptive syntacticians. Thus, using TAG, one can take advantage in the construction of parsers and learners of the computational tractability of a mathematically restrictive formalism without having to reinvent empirical syntax in order to do so. At the same time, TAG analyses are not identical in every detail to their transformational counterparts; and it is interesting to compare them where they diverge. The differences arise because of a fundamental difference in the way that syntactic recursion is treated in the two frameworks. In TAG, recursive structures are generated by composing elementary syntactic objects, with the result that recursion is factored apart from the representation of local syntactic dependencies. By contrast, in transformational grammar, as in many other frameworks, recursive structure and local dependencies are represented together in a single, full representation of a complex sentence. Because of this difference in the treatment of recursion, it often turns out, when TAG is used to emulate a transformational analysis, that the TAG version has advantages, of both elegance and empirical coverage, over the original. This paper is a demonstration in a new empirical domain, that of nominal constructions, of the advantages of TAG‐based syntax. By presenting a linguistically detailed account of these constructions and showing the advantages of using TAG to analyze them, we strengthen the case for the use of mathematically constrained and computationally tractable representational systems in competence‐based as well as in computational linguistics.
SYNTAX OR SEMANTICS? HANDLING NONLOCAL DEPENDENCIES WITH MCTAGS OR SYNCHRONOUS TAGS
Authors: Abeillé Anne
Published: April 2007

We show how multicomponent TAGs, although in their “local” version equivalent to “simple” TAGs, enable one to associate the derived structures with a richer set of derivations. This is especially useful for representing some nonlocal dependencies such as wh‐extraction out of NP or extraposition, as soon as one interprets the derivation structures as representing the predicate‐argument dependencies. However, there is a formal alternative in the formalism of synchronous TAGs that achieves a similar result, namely, that associates standard syntactic derivations with nonisomorphic semantic derivations, and relies on the latter to represent the dependency relations. We show that the latter treatment accounts for a different range of extraposition facts in French, where the relationship between the head noun and its extraposed dependent is a semantic one.

Nous montrons comment les TAGs ensemblistes “locales” (MCTAGs), qui sont équivalentes aux TAGs simples, permettent ?associer aux structures syntaxiques dérivées un ensemble plus large de structures dérivationnelles. Cela est particulièrement utile pour la représentation des dépendances non locales qu'on observe dans les extractions hors du groupe nominal et les extrapositions, à partirdu moment oùľon interprète les arbres de dérivation comme représentant les relations de dépendance. II existe toutefois une autre possibilityé dans le cadre des TAGs synchrones qui associe aux dérivations syntaxiques standard des dérivations sémantiques non isomorphes et interprète les relations de dépendance en se basant sur ces dernières. Nous montrons que cette deuxième possibilityé est mieux adaptée pour des cas ?extraposition en français où la relation de dépendance entre le nom těte et ľélément extraposé est ?ordre sémantique.
LEFT TO RIGHT PARSING OF LEXICALIZED TREE‐ADJOINING GRAMMARS1
Authors: Schabes Yves
Published: April 2007

This paper presents an algorithm (a parser) for analyzing sentences according to grammatical constraints expressed in the framework of lexicalized tree‐adjoining grammar. For the current grammars of English, the algorithm behaves much better and requires much less time than its worst‐case complexity. The main objective of this work is to design a practical parser whose average‐case complexity is much superior to its worst case. Most of the previous methods always required the worst‐case complexity. The algorithm can be used in two modes. As a recognizer it outputs whether the input sentence is grammatically correct or not. As a parser it outputs a detailed analysis of the grammatically correct sentences. As sentences are read from left to right, information about possible continuations of the sentence is computed. In this sense, the algorithm is called a predictive left to right parser. This feature reduces the average time required to process a given sentence. In the worst case, the parser requires an amount of time proportional to G2n6 for a sentence of n words and for a lexicalized tree‐adjoining grammar of size G. The worst‐case complexity is only reached with pathological (not naturally occurring) grammars and inputs.
PREDICTIVE LEFT‐TO‐RIGHT PARSING OF A RESTRICTED VARIANT OF TAG(LD/LP)
Authors: Minnen Guido
Published: April 2007

By means of a factorization of linear precedence (LP) information in tree‐adjoining grammar (TAG), the possibility to capture syntactic generalizations can be enhanced, especially with respect to languages which exhibit relative free word‐order. In TAG(LD/LP) LP‐information is factorized in a way reminiscent of the ID/LP format of CFGs. However, in contrast to its context‐free counterpart, in TAG(LD/LP) entanglement of constituents is allowed by admitting not only the permutation of sister nodes, but also of non‐sister nodes in a structural description. In this paper a generalization of the predictive left‐to‐right parser for TAG is presented which is able to handle a restricted variant of TAG(LD/LP), which allows the permutation of sister nodes and non‐sister nodes within elementary structures, the basic building blocks of TAG(LD/LP).
SIMPSON'S PARADOX IN ARTIFICIAL INTELLIGENCE AND IN REAL LIFE
Authors: Neufeld Eric
Published: April 2007

“Simpson's paradox,” first described nearly a century ago, is an anomaly that sometimes arises from pooling data. Dramatic instances of the paradox have occurred in real life in the domains of epidemiology and admissions policies. Many writers have recently described hypothetical examples of the paradox arising in other areas of life and it seems possible that the paradox may occur frequently in mundane domains but with less serious implications. Thus, it is not surprising that the paradox should arise in commonsense reasoning, that subarea of artificial intelligence that seeks to axiomatize reasoning in such mundane domains. It arises as the problem “approximate proof by cases” and the question of whether to accept it may well depend on whether we wish to construct performance or competence models of reasoning. This article gives a brief history of the paradox and discusses its occurrence in our own discipline. It argues that if the paradox occurs frequently but undramatically in real life, every uncertain reasoning system will have to deal with the problem in some way.
A FRAMEWORK FOR LOGICS OF EXPLICIT BELIEF
Authors: Delgrande James P.
Published: April 2007

The epistemic notions of knowledge and belief have most commonly been modeled by means of possible worlds semantics. In such approaches an agent knows (or believes) all logical consequences of its beliefs. Consequently, several approaches have been proposed to model systems of explicit belief, more suited to modeling finite agents or computers. In this paper a general framework is developed for the specification of logics of explicit belief. A generalization of possible worlds, called situations, is adopted. However the notion of an accessibility relation is not employed; instead a sentence is believed if the explicit proposition expressed by the sentence appears among a set of propositions associated with an agent at a situation. Since explicit propositions may be taken as corresponding to “belief contexts” or “frames of mind,” the framework also provides a setting for investigating such approaches to belief. The approach provides a uniform and flexible basis from which various issues of explicit belief may be addressed and from which systems may be contrasted and compared. A family of logics is developed using this framework, which extends previous approaches and addresses issues raised by these earlier approaches. The more interesting of these logics are tractable, in that determining if a belief follows from a set of beliefs, given certain assumptions, can be accomplished in polynomial time.
EXTRACTING LAWS FROM DECISION TABLES: A ROUGH SET APPROACH
Authors: Skowron A.
Published: April 2007

We present some methods, based on the rough set and Boolean reasoning approaches, for extracting laws from decision tables. First we discuss several procedures for decision rules synthesis from decision tables. Next we show how to apply some near‐to‐functional relations between data to data filtration. Two methods of searching for new classifiers (features) are described: searching for new classifiers in a given set of logical formulas, and searching for some functions approximating near‐to‐functional relations.
AN INTUITIVE MOTIVATION OF BAYESIAN BELIEF MODELS
Authors: Snow Paul
Published: April 2007

The general use of subjective probabilities to model beliefs has been justified using many axiomatic schemes. This paper presents a rationale for probability models based on intuitive properties of belief orderings and the effect of evidence on beliefs. Qualitative probability, which imposes stringent constraints on belief representation schemes, is derived from four simple assumptions about beliefs and evidence. Properties shown to be sufficient for the adoption of probability proper by Cox (1978) are derived here from qualitative probability and a principle of plausible reasoning advanced by Polya (1954). Models based on complete orderings of beliefs extend easily to motivate set‐valued representations of partial orderings as well.
A NEW METHOD FOR INFLUENCE DIAGRAM EVALUATION
Authors: Qi Runping , Poole David
Published: April 2007

As influence diagrams become a popular representational tool for decision analysis, influence diagram evaluation attracts more and more research interests. In this article, we present a new, two‐phase method for influence diagram evaluation. In our method, an influence diagram is first mapped onto a decision graph and then the analysis is carried out by evaluating the decision graph. Our method is more efficient than Howard and Matheson's because, among other reasons, our method generates a much smaller decision graph for the same influence diagram. Like those most recent algorithms reported in the literature, our method also provides a clean interface between influence diagram evaluation and Bayesian net evaluation. Consequently, various well‐established algorithms for Bayesian net evaluation can be used in influence diagram evaluation. Furthermore, our method has a few unique merits. First, it takes advantage of asymmetry in influence diagrams to avoid unnecessary computation. Second, by using heuristic search techniques, it provides an explicit mechanism for using heuristic information that may be available in a domain‐specific form. These additional merits make our method more efficient than the current algorithms in general. Finally, by using decision graphs as an intermediate representation, the value of perfect information can be computed in a more efficient way.
SOLVING NINE MEN'S MORRIS
Authors: Gasser Ralph
Published: April 2007

The game of Nine Men's Morris is a draw. We obtained this result using a combination of endgame databases (1010 states) and search. Our improved algorithm for computing endgame databases allowed the game to be solved on a personal computer. Other games have been solved using knowledge‐based methods to dramatically prune the search tree. Nine Men's Morris does not seem to profit from such methods, making it the first nontrivial game solved in which almost the entire state space has to be considered.
GENERAL GAME‐PLAYING AND REINFORCEMENT LEARNING
Authors: Levinson Robert
Published: April 2007

This paper provides a blueprint for the development of a fully domain‐independent single‐agent and multiagent heuristic search system. It gives a graph‐theoretic representation of search problems based on conceptual graphs and outlines two different learning systems. One, an “informed learner”, makes use of the graph‐theoretic definition of a search problem or game in playing and adapting to a game in the given environment. The other, a “blind learner”, is not given access to the rules of a domain but must discover and then exploit the underlying mathematical structure of a given domain. Relevant work of others is referenced within the context of the blueprint.

To illustrate further how one might go about creating general game‐playing agents, we show how we can generalize the understanding obtained with the Morph chess system to all games involving the interactions of abstract mathematical relations. A monitor for such domains has been developed, along with an implementation of a blind and informed learning system known as Morphll. Performance results with MorphK are preliminary but encouraging and provide a few more data points with which to understand and evaluate the blueprint.
LEARNING MONOTONIC‐CONCAVE INTERVAL CONCEPTS USING THE BACK‐PROPAGATION NEURAL NETWORKS
Authors: Wang Shouhong
Published: April 2007

Monotonicity and concavity play important roles in human cognition, reasoning, and decision making. This paper shows that neural networks can learn monotonic‐concave interval concepts based on real‐world data, Traditionally, the training of neural networks has been based only on raw data. In cases where the training samples carry statistical fluctuations, the products of the training have often suffered. This paper suggests that global knowledge about monotonicity and concavity of a problem domain can be incorporated in neural network training. This paper proposes a learning scheme for the back‐propagation layered neural networks in learning monotonic‐concave interval concepts and provides an example to show its application.
ON THE IMPLEMENTATION AND EVALUATION OF AbTweak
Authors: Yang Qiang , Tenenberg Josh D. , Woods Steven
Published: April 2007

In this paper, we describe the implementation and evaluation of the AbTweakplanning system, a test bed for studying and teaching concepts in partial‐order planning, abstraction, and search control. We start by extending the hierarchical, precondition‐elimination abstraction of ABSTRIPS to partial‐order‐based, least‐commitment planners such as Tweak. The resulting system, AbTweak, illustrates the advantages of using abstraction to improve the efficiency of search. We show that by protecting a subset of abstract conditions achieved so far, and by imposing a bias on search toward deeper levels in a hierarchy, planning efficiency can be greatly improved. Finally, we relate AbTweakto other planning systems SNLP, ALPINE, and SIPE by exploring their similarities and differences.
A STRENGTHENED ALGORITHM FOR TEMPORAL REASONING ABOUT PLANS
Authors: Song Fei , Cohen Robin
Published: April 2007

Allen's interval algebra has been shown to be useful for representing plans. We present a strengthened algorithm for temporal reasoning about plans, which improves on straightforward applications of the existing reasoning algorithms for the algebra. This is made possible by viewing plans as both temporal networks and hierarchical structures. The temporal network view allows us to check for inconsistencies as well as propagate the effects of new temporal constraints, whereas the hierarchical view helps us to get the strengthened results by taking into account the dependency relationships between actions.

We further apply our algorithm to the process of plan recognition through the analysis of natural language input. We show that such an application has two useful effects: the temporal relations derived from the natural language input can be used as constraints to reduce the number of candidate plans, and the derived constraints can be made more specific by combining them with the prestored constraints in the plans being recognized.
DOMAIN‐INDEPENDENT TEMPORAL REASONING WITH RECURRING EVENTS
Authors: Morris RobertA. , Shoaff WilliamD. , Khatib Lina
Published: April 2007

Numerous examples of temporal reasoning involve a process of abstraction from the number of times an event is to occur or the number of times events stand in a temporal relation. For example, scheduling a recurring event such as one's office hours may consider things like the relative temporal ordering of the office hours and a number of other events in a given work day. The number of times office hours will actually be held may be unknown, even irrelevant, at the time of scheduling them. The objective of this article is to formulate a domain‐independent framework for reasoning about recurring events and their relations. To achieve this end, we propose an ontology of recurrence based on the model‐theoretic structure underlying collective predication using plural noun phrases. We offer a calculus of binary temporal relations for temporal collections based on a well‐defined transformation of interval temporal relations into recurrence relations. Finally, we describe a reasoning framework based on manipulating knowledge stored in temporal relation networks, which is in turn a specialization of the CSP (constraint satisfaction problem) framework. The reasoner manipulates recurrence relations in the network to determine the network's consistency or to generate scenarios.
EVENT TRACKING IN A DYNAMIC MULTIAGENT ENVIRONMENT
Authors: Tambe Milind , Rosenbloom Paul S.
Published: April 2007

In a dynamic, multiagent environment, an automated intelligent agent is often faced with the possibility that other agents may instigate events that hinder or help the achievement of its own goals. To act intelligently in such an environment, an automated agent needs an event tracking capability to continually monitor the occurrence of such events and the temporal relationships among them. This capability enables an agent to infer the occurrence of important unobserved events as well as to obtain a better understanding of the interaction among events. This article focuses on event tracking in one complex and dynamic multiagent environment: the air‐combat simulation environment. It analyzes the challenges that an automated pilot agent must face when tracking events in this environment. This analysis reveals three new issues that have not been addressed in previous work in this area: (i) tracking events generated by agents’ flexible and reactive behaviors, (ii) tracking events in the context of continuous agent interactions, and (iii) tracking events in real time. This article proposes one solution to address these issues. One key idea in this solution is that the (architectural) mechanisms that an agent employs in generating its own flexible and reactive behaviors can be used to track other agents’ flexible and reactive behaviors in real time. A second key idea is the use of a world‐centered representation for modeling agent interactions. The solution is demonstrated using an implementation of an automated pilot agent.
VALIDATION OF FIRST‐ORDER RULE‐BASED SYSTEMS1
Authors: Cordier M. O. , Loiseau S.
Published: April 2007

Knowledge base validation and knowledge base refinement aim to help the expert to improve an existing knowledge base. They deal with the final knowledge acquisition phase and rely on a quality measurement of an existing knowledge base. We present our approach to knowledge base refinement, which is based on results in the domain of knowledge base validation. Our approach is based on a general consistency definition of a knowledge base and on a study of causes of knowledge base inconsistency. Our approach relies significantly on a differentiation of sure and expert knowledge in the knowledge base. We have implemented a system that has two phases: one computational phase decides on the consistency of a knowledge base, and, if necessary, a second phase helps the expert to interactively update the knowledge base. We present some related work in the domain. We illustrate the use of our system with an example.
RECURRENT NEURAL NETWORKS AND FINITE AUTOMATA
Authors: Siegelmann Hava T.
Published: April 2007

This article studies finite size networks that consist of interconnections of synchronously evolving processors. Each processor updates its state by applying an activation function to a linear combination of the previous states of all units. We prove that any function for which the left and right limits exist and are different can be applied to the neurons to yield a network which is at least as strong computationally as a finite automaton. We conclude that if this is the power required, one may choose any of the aforementioned neurons, according to the hardware available or the learning software preferred for the particular application.
MODELING EQUILIBRIUM REGIONAL INTEGRATION BY ENDOGENISING MARGINAL COST IN THE COURNOT FRAMEWORK
Authors: Gangopadhyay Partha
Published: April 2007

This paper examines the formation of endogenous alliances between local firms and multinational enterprises (MNE), which in turn drives regional integration in the global economy. The proposed model is an extension of the Cournot duopoly with linear demand, in which the cost function is predicated on the size of local alliance that can be interpreted as the scale of operation. The paper also makes a departure by assuming managers are not only motivated by profits, but also by the scale of operation or “empire building”. Forward‐looking MNEs strategize their current alliance formation activities from whence we derive a Nash equilibrium configuration of regional integration. We demonstrate that the equilibrium can be beset with multiplicity, indeterminacy, fragility, and chaotic regimes.
Individualized Statistics Coursework Using Spreadsheets
Authors: Hunt Neville
Published: April 2007

This article describes how a spreadsheet‐based tool can be used to allocate each student in a class a unique subset of a large set of data, as the basis for a statistical assignment.
Clasping Hands and Folding Arms: A Data Investigation
Authors: MacGillivray Helen
Published: April 2007

This is the first of a series on data investigations in which the cycle of issues, planning, collecting, exploring, interpreting and discussing is reported for selected data investigations, with the data sets available on the Blackwell repository. The motivating issues for the investigation of this report were the manner in which people clasp their hands and fold their arms. The data set yields some interesting aspects for students, for teaching and for future or further investigations, and illustrates the needs for systematic and thoughtful exploration of data.
Measuring Marbles: Demonstrating the Basic Tenets of Measurement Theory
Authors: Wininger Steven R.
Published: April 2007

A hands‐on activity is described in which students attempt to measure something that they cannot see. In small groups, students estimate the number of marbles in sealed boxes. Next, students’ estimates are compared with the actual numbers. Last, values from both the students’ estimates and actual numbers are used to explain measurement theory and reliability.
There is no ‘truth’ outside a context: implications for the teaching of analytical psychology in the 21st century
Authors: Horne Michael
Published: April 2007

Abstract:  Humans are from birth embedded in a historical and contemporary context of meanings. This always constrains their theoretical and practical activities. In this paper, I will be suggesting that there are no guiding ‘truths’ outside such contexts. In order to understand the foundations of any concept or new idea, it is important to comprehend the context in which it is embedded. Candidates and some of their teachers have very little knowledge of the intellectual context in which Jung or any other analytic theorist wrote. As a result, the analytic ‘founders’ are often believed to have discovered ‘truths’ transcending the context of history and of everyday life. They were, however, as much creative synthesizers as pure originators.

I propose that the components of all analytic theories emerge from their embeddedness. I contend, therefore, that the understandings of these components such as psychic causality, epistemology and identity formation were quite differently conceived at the time the analytic founders were working than they are today. I will give examples to show how the acceptance of this attitude is useful in inculcating a discerning approach in candidates towards traditionally accepted analytic theories and practices. This can provide them with a method to promote their individual creative development.