bluuebunny/crossref_metadata_2025 huggingface dataset:
The design of the SCENT automated advisor
Authors: McCalla Gordon I. , Bunt Richard B. , Harms Janelle J.
Published: April 2007

The SCENT (Student Computing ENvironmenT) project is concerned with building an intelligent tutoring system to help student programmers debug their LISP programs. The major thrust of current SCENT investigations is into the design of the SCENT advisor which is meant to provide debugging assistance to novice students. Six conceptual levels constitute the advisor. At the lowest level is the “raw data,” consisting of the student's (possibly buggy) program. This can be interpreted by a “program behaviour” level which can produce traces, cross‐reference charts, etc. from the student's program. These traces, etc. can be analyzed by “observers” for interesting patterns. At the next level are “strategy judges” and “diagnosticians” which determine which strategy the student has used in his/her program and bugs in this strategy. A “task expert” provides task‐specific input into the process of analyzing the student's solution, and a “student‐knowledge component” provides student‐specific input into this process. Information from the six levels interacts in a variety of ways and control is similarly hierarchical. This necessitates a blackboard‐style scheme to coordinate information dissemination and control flow.

This paper discusses the objectives of SCENT and focusses on organizing the process of debugging student programs. A complete example is given to illustrate how entities at the six levels interact and to indicate the kinds of information sharing that occur in the SCENT advisor. The paper concludes with an evaluation of the strengths and weaknesses of this approach to automated debugging, and suggestions about directions for further exploration.
An explanation shell for expert systems
Authors: Sterling Leon , Lalee Marucha
Published: April 2007

We describe a shell for expert systems written in Prolog. The shell provides a consultation environment and a range of explanation capabilities. The design of the shell is modular, making it very easy to extend the shell with extra features required by a particular expert system. The novelty of the shell is twofold. Firstly, it has a uniform design consisting of an integrated collection of meta‐interpreters. Secondly, there is a new approach for explaining ‘why not,’ when a query to the system fails.
Automatic program debugging for intelligent tutoring systems
Authors: Murray William R.
Published: April 2007

Program debugging is an important part of the domain expertise required for intelligent tutoring systems that teach programming languages. This article explores the process by which student programs can be automatically debugged in order to increase the instructional capabilities of these systems. The research presented provides a methodology and implementation for the diagnosis and correction of nontrivial recursive programs. In this approach, recursive programs are debugged by repairing induction proofs in the Boyer‐Moore logic. The induction proofs constructed and debugged assert the computational équivalence of student programs to correct exemplar solutions. Exemplar solutions not only specify correct implementations but also provide correct code to replace buggy student code. Bugs in student code are repaired with heuristics that attempt to minimize the scope of repair.

The automated debugging of student code is greatly complicated by the tremendous variability that arises in student solutions to nontrivial tasks. This variability can be coped with, and debugging performance improved, by explicit reasoning about computational semantics during the debugging process. This article supports these claims by discussing the design, implementation, and evaluation ofTalus,an automatic debugger for LISP programs, and by examining related work in automated program debugging.

Talus relies on its abilities to reason about computational semantics to perform algorithm recognition, infer code teleology, and to automatically detectandcorrect nonsyntactic errors in student programs written in a restricted, but nontrivial, subset of LISP. Solutions can vary significantly in algorithm, functional decomposition, role of variables, data flow, control flow, values returned by functions, LISP primitives used, and identifiers used. Solutions can consist of multiple functions, each containing multiple bugs. Empiricial evaluation demonstrates that Talus achieves high performance in debugging widely varying student solutions to challenging tasks.
LIY: learn‐it‐yourself software interfaces
Authors: Martin F. A.
Published: April 2007

An increasing number of people are becoming users of unfamiliar software. They can be genuinely “new” computer users or part of a growing group who are transferring skills and knowledge from a familiar product such as a word processor to a functionally similar, but different, unfamiliar one. The problem for users in this position is that they do not have access to training courses to teach them how to use such software and are usually forced to rely on text‐based documentation. LIY is a method for producing computer‐based tutorials to teach the user ofasoftware product.This paper describes how LIY is, in turn, (1) a method for application system design which recognizes the need for tutorial design (a task analysis and user interface specification provide information structures that are passed to the tutorial designer); (2) a support environment for the tutorial designer (in addition to prompting for courseware for nodes in the task analysis, LIY provides a ready‐made rule base for constraining the degree of learner control available while the tutorial is in use. The designer is able to tailor this rule base for a specific tutorial); and (3) a tutorial delivery environment (the tutorial adapts to individual learners and offers a degree of learner control).
Equivalent logic programs and symmetric homogeneous forms of logic programs with equality
Authors: Chan Kwok Hung
Published: April 2007

This article introduces the notion of CAS‐equivalent logic programs: logic programs with identical correct answer substitutions. It is shown that the notions CAS‐equivalence, refutational equivalence, and logical equivalence do not coincide in the case of definite clause logic programs. Least model criteria for refutational and CAS‐equivalence are suggested and their correctness is proved. The least model approach is illustrated by two proofs of CAS‐equivalence. It is shown that the symmetric extension of a logic program subsumes the symmetry axiom and the symmetric homogeneous form of a logic program with equality subsumes the symmetry, transitivity, and predicate substitutivity axioms of equality. These results contribute towards the goal of building equality into standard Prolog without introducing additional inference rules.
Cohesion methods in inductive learning
Authors: Abbott Lynn
Published: April 2007

According to Webster, cohesion is “the act or process of sticking together tightly.” Here the term represents the underlying forces that drive the formation of classes during inductive learning. This paper considers several numerical and conceptual induction algorithms, and compares their methods of cohesion. While these algorithms represent several different methods, they also exhibit some significant commonalities.
Logical omniscience, semantics, and models of belief
Authors: Hadley Robert F.
Published: April 2007

Logical omniscience may be described (roughly) as the state of affairs in which an agent explicitly believes anything which is logically entailed by that agent's beliefs. It is widely agreed that humans are not logically omniscient, and that an adequate formal model of belief, coupled with a correct semantic theory, would not entail logical omniscience. Recently, two prominent models of belief have emerged which purport both to avoid logical omniscience and to provide an intuitively appealing semantics. The first of these models is due to Levesque (1984b); the second to Fagin and Halpem (1985). It is argued herein that each of these models faces serious difficulties. Detailed criticisms are presented for each model, and a computationally oriented theory of intensions is presented which provides the foundation for a new formal model of belief. This formal model is presented in a decidable subset of first‐order logic and is shown to provide a solution to the general problem of logical omniscience. The model provides for the possibility of belief revision and places no a priori restrictions upon an agent's representation language.
An inquiry into computer understanding
Authors: Cheeseman Peter
Published: April 2007

This essay addresses a number of issues centered around the question of what is the best method for representing and reasoning about common sense (sometimes called plausible inference). Drew McDermott has shown that a direct translation of commonsense reasoning into logical form leads to insurmountable difficulties, from which McDermott concluded that we must resort to procedural ad hocery. This paper shows that the difficulties McDermott described are a result of insisting on using logic as the language of commonsense reasoning. If, instead, (Bayesian) probability is used, none of the technical difficulties found in using logic arise. For example, in probability, the problem of referential opacity cannot occur and nonmonotonic logics (which McDermott showed don't work anyway) are not necessary. The difficulties in applying logic to the real world are shown to arise from the limitations of truth semantics built into logic–probability substitutes the more reasonable notion of belief. In Bayesian inference, many pieces of evidence are combined to get an overall measure of belief in a proposition. This is much closer to commonsense patterns of thought than long chains of logical inference to the true conclusions. Also it is shown that English expressions of the “IF A THEN B” form are best interpreted as conditional probabilities rather than universally quantified expressions. Bayesian inference is applied to a simple example of linguistic information to illustrate the potential of this type of inference for AI. This example also shows how to deal with vague information, which has so far been the province of fuzzy logic. It is further shown that Bayesian inference gives a theoretical basis for inductive inference that is borne out in practice. Instead of insisting that probability is the best language for commonsense reasoning, a major point of this essay is to show that real inference is a complex interaction between probability, logic, and other formal representation and reasoning systems.
What kind of thing is a concept?
Authors: Kayser Daniel
Published: April 2007

We discuss several features of concepts used for common knowledge and argue that these features are not superficial, lexical level language‐dependent issues, but deep characteristics of the knowledge itself. It is thus necessary to build knowledge representation systems compatible with these characteristics.

We show that the most common suggestions to cope with typicality (e.g., many‐valued and (or) nonmonotonic systems) fail to capture entirely this phenomenon. As for the other features, no serious attempt has been made yet, and we only propose tentative elements for a solution.

The main idea is to decouple the notion of concept from the notion of basic element (predicate, node), and to represent a concept by an open‐ended family of entities of the system. Each entity conveys a possible interpretation of the concept, and interpretations are ordered, according to their “depth.” An example illustrating the main features of this scheme is provided.
On the consistency of knowledge bases: the COVADIS system
Authors: Rousset Marie‐Christine
Published: April 2007

It is currently thought in the knowledge‐based systems (KBS) domain that sophisticated tools are necessary for helping an expert with the difficult task of knowledge acquisition. The problem of detecting inconsistencies is especially crucial. The risk of inconsistencies increases with the size of the knowledge base; for large knowledge bases, detecting inconsistencies “by hand” or even by a superficial survey of the knowledge base is impossible. Indeed, most inconsistencies are due to the interaction between several rules via often deep deductions. In this paper, we first state the problem and define our approach in the framework of classical logic. We then describe a complete method to prove the consistency (or the inconsistency) of knowledge bases that we have implemented in the COVADIS system.
Representation and combination of uncertainty with belief functions and possibility measures
Authors: Dubois Didler , Prade Henri
Published: April 2007

The theory of evidence proposed by G. Shafer is gaining more and more acceptance in the field of artificial intelligence, for the purpose of managing uncertainty in knowledge bases. One of the crucial problems is combining uncertain pieces of evidence stemming from several sources, whether rules or physical sensors. This paper examines the framework of belief functions in terms of expressive power for knowledge representation. It is recalled that probability theory and Zadeh's theory of possibility are mathematically encompassed by the theory of evidence, as far as the evaluation of belief is concerned. Empirical and axiomatic foundations of belief functions and possibility measures are investigated. Then the general problem of combining uncertain evidence is addressed, with focus on Dempster rule of combination. It is pointed out that this rule is not very well adapted to the pooling of conflicting information. Alternative rules are proposed to cope with this problem and deal with specific cases such as nonreliable sources, nonexhaustive sources, inconsistent sources, and dependent sources. It is also indicated that combination rules issued from fuzzy set and possibility theory look more flexible than Dempster rule because many variants exist, and their numerical stability seems to be better.
Casual reasoning in planning1
Authors: Wilkins David E.
Published: April 2007

Reasoning about actions necessarily involves tracking the truth of assertions about the world over time. The SIPE planning system retains the efficiency of the STRIPS assumption for this while enhancing expressive power by allowing the specification of a causl theory. Separation of knowledge about causality from knowledge about actions relieves operators of much of their representational burden and allows them to be applicable in a wide range of contexts. The implementation of causal theories is described, together with examples and evaluations of the system's expressive power and efficiency.
Exhuming the criticism of the logicist
Authors: Goebel Randy
Published: April 2007

McDermott has recently explained his fundamental philosophical shift on the methodology of artificial intelligence (AI) and has further suggested that the shift is both necessary and inevitable. The shift results from a perception that a trend towards overformalisation has detached the real problems from the research results. McDermott's criticism is an enlightened exhumation of the criticisms of the seventies and explains new ways in which the logical methodology can be abused. I argue that McDermott's criticism should not discourage the use of logic, but force a timely reexamination of its fundamental role in AI.
A model for reasoning about persistence and causation
Authors: Dean Thomas , Kanazawa Keiji
Published: April 2007

Reasoning about change requires predicting how long a proposition, having become true, will continue to be so. Lacking perfect knowledge, an agent may be constrained to believe that a proposition persists indefinitely simply because there is no way for the agent to infer a contravening proposition with certainty. In this paper, we describe a model of causal reasoning that accounts for knowledge concerning cause‐and‐effect relationships and knowledge concerning the tendency for propositions to persist or not as a function of time passing. Our model has a natural encoding in the form of a network representation for probabilistic models. We consider the computational properties of our model by reviewing recent advances in computing the consequences of models encoded in this network representation. Finally, we discuss how our probabilistic model addresses certain classical problems in temporal reasoning (e. g., the frame and qualification problems).
A logic programming approach to cartographic map overlay
Authors: Wu Peter Y. F. , Franklin W. Randolph
Published: April 2007

Cartographic map overlay is the process of superimposing two maps into one to convey information in spatial correlation. A map refers to one in vector representation: a two‐dimensional spatial data structure of nodes, chains, and polygons. We present a map overlay system developed in Prolog. The system adopts a relational approach to data structuring. We represent geometric entities and their relationships as facts, and encode geometry algorithms in the rules. Set‐based operations perform data processing. To speed up the search for chain intersections, a uniform rectangular grid is imposed over the object space for spatial sorting by distribution. We sort out potentially intersecting edge segments to those occupying some common grid cell. Each bucket, if non‐empty, is implemented as a Prolog fact identifying the grid cell for random access. Geometric intersections are calculated using exact rational arithmetic implemented in Prolog. Numerical accuracy is preserved and we can identify all the special cases of tangent conditions. We can then guarantee topological consistency, and stability in the process of map overlay is therefore achieved.
Intelligent computer‐aided‐design systems: a synergical approach of artificial intelligénce and engineering
Authors: Pu Pearl
Published: April 2007

A synergism has begun to surface from the artificial intelligence (AI) and engineering communities: an effort to apply AI techniques to engineering problem‐solving activities, and to study problems arisen from various engineering fields as a way to develop AI theories and methodologies. This paper first discusses the needs of such a synergical approach and identifies in a broad perspective some AI techniques currently being applied to engineering. It then describes a system, called KREATOR, which applies qualitative reasoning, a subfield of AI, to computer‐aided design (CAD). The key observation is that an engineer designer's qualitative knowledge can offer a good basis for the reasoning of device behaviors. Such knowledge, however, is not captured by conventional CAD systems for lack of good representations. KREATOR is a knowledge capturing scheme that allows the designers to record their qualitative knowledge of how mechanical devices behave, KREATOR then automatically generates qualitative simulations.
Time revisited1
Authors: Miller Stephanie A. , Schubert Lenhart K.
Published: April 2007

Temporal reasoning is essential for many artificial intelligence applications. To date, most research has concentrated on temporal inference in isolation without considering the role it can play in a more general reasoning environment. This paper takes an efficient temporal reasoner and extends its inferential capabilities to handle both strict and nonstrict relations. The resulting temporal specialist is incorporated into a system intended for low‐level reasoning in natural language understanding. The specialist assists the resolution‐based theorem prover in function evaluation, literal evaluation, and generalized resolving and factoring. The combined system can do some proofs in just a few steps that would normally require many. An example from the fully operational hybrid system is included.

Le raisonnement temporel est essentiel dans de nombreuses applications relatives àľ intelligence artificielle. Jusqu’à présent, la plupart des travaux de recherche ont porté sur ľ inférence temporelle dans ľ isolation sans tenir compte du rǒle qu'elle peut jouer dans un environnement de raisonnement plus général. Cet article traite ? un raisonneur temporel ef ficace dont les capacityés inférentielles ont été augmentée afin de pouvoir traiter les relations strides et non strides. Le spécialiste temporel qui en résulte est intégréà un système conçu pour le raisonnement bas‐niveau en langage naturel. Le spécialiste assiste le démonstratur de théorèmes basé sur la résolution dans ľévaluation des fonctions, ľévaluation littérale et la fonction fadorielle généralisée. Le système combine peut vérifier des preuves en quelques étapes seulement au lieu ? un grand nombre. Un exemple ? un système hybride entièrement opérationnel est fourni.

Mots clés: raisonnement temporel, methodes ? inférence spéciales, résolution de théories, représentation des connaissances.
Modeling the user's conceptual knowledge in BGP‐MS, a user modeling shell system1
Authors: Kobsa Alfred
Published: April 2007

The paper describes the modeling of a user's conceptual knowledge in the general user modeling shell system BGP‐MS. On the one hand, BGP‐MS is a workbench for the develment of a user model in a particular application domain. It supports the definition of the architecture of the individual user model, and of the architecture and the contents of user stereotypes. A rich representation language for conceptual knowledge, a partition mechanism, and flexible graphics‐based interfaces are at the disposal of the user model developer. On the other hand, BGP‐MS is a runtime user modeling tool aimed at fulfilling central tasks of a user modeling component in an application system. In this mode, the system offers a functional interface for accessing and updating the model of the current user, as well as basic domain‐independent inference mechanisms, support for inferences defined by the developer, and a customizable stereotype management utility. The usefulness of BGP‐MS will be demonstrated by illustrating how it can support the user modeling of various recently developed application systems.
Learning in relational databases: an attribute‐oriented approach
Authors: CAI YANDONG , CERCONE NICK , HAN JIAWEI
Published: April 2007

The development of efficient algorithms for learning from large relational databases is an important task in applicative machine learning. In this paper, we study knowledge discovery in relational databases and develop an attribute‐oriented learning method which extracts generalization rules from relational databases. The method adopts the artificial intelligence “learning‐from‐examples” paradigm and applies in the learning process an attribute‐oriented concept tree ascending technique which integrates database operations with the learning process and provides a simple and efficient way of learning from databases. The method learns both characteristic rules and classification rules of a learning concept, where a characteristic rule characterizes the properties shared by all the facts of the class being learned; while a classification rule characterizes the properties that distinguish the class being learned from other classes. The learning result could be a conjunctive rule or a rule with a small number of disjuncts. Moreover, learning can be performed with databases containing noisy data and exceptional cases using database statistics. Our analysis of the algorithms shows that attribute‐oriented induction substantially reduces the computational complexity of the database learning process.

Le développement d'algorithmes efficaces permettant l'apprentissage à partir de bases de donnees relationnelles est une fonction importante de l'apprentissage automatique applicatif. Dans cet article, les auteurs examinent la découverte des connaissances dans les bases de données relationnelles et élaborent une méthode d'apprentissage orientée sur l'attribut qui extrait des bases de données relationnelles les règies de généralisation. La méthode adopte le paradigme d'apprentissage à partir d'exemples et applique au processus d'apprentissage la technique de l'arbre des concepts orientés sur l'attribut qui incorpore les opérations de base de données au processus d'apprentissage, ce qui permet d'obtenir une méthode simple et efficace d'apprentissage à partir des bases de données. La méthode fait l'apprentissage des règies caractéristiques et des règies de classification d'un concept d'apprentissage; la règie caractéristique qualifie les pro‐priétés communes à tous les faits d'une categorie faisant l'objet d'un apprentissage alors que la règie de classification caractérise les propriétés qui distinguent la catégorie faisant l'objet d'un apprentissage des autres catégories. Le résultat peut ětre une règie conjonctive ou une règie ayant un petit nombre de disjonctifs. Qui plus est, 1′apprentissage peut se faire avec des bases de données contenant des donnees bruitees et des cas exceptionnels utilisant des statistiques de bases de données. L'analyse des algorithmes démontre que l'induction orientée sur l'attribut réduit considérablement la complexité informàtique du processus d'apprentissage des bases de données.
Generation and synchronous tree‐adjoining grammars
Authors: Shieber Stuart M. , Schabes Yves
Published: April 2007

Tree‐adjoining grammars (TAG) have been proposed as a formalism for generation based on the intuition that the extended domain of syntactic locality that TAGs provide should aid in localizing semantic dependencies as well, in turn serving as an aid to generation from semantic representations. We demonstrate that this intuition can be made concrete by using the formalism of synchronous tree‐adjoining grammars. The use of synchronous TAGs for generation provides solutions to several problems with previous approaches to TAG generation. Furthermore, the semantic monotonicity requirement previously advocated for generation grammars as a computational aid is seen to be an inherent property of synchronous TAGs.
Content determination in the generation of referring expressions
Authors: Dale Robert , Haddock Nicholas
Published: April 2007

In this paper, we describe a general framework for the generation of referring expressions. Given an intended referent in the domain, domain‐dependent mapping rules build a domain‐independent level ofrecoverable semantic structure,which encodes the semantic content to be recovered by the hearer; a second set of mapping rules then builds anabstract syntactic structure,which is unified with a grammar and lexicon to produce a surface noun phrase. Within this framework, (0 we present a detailed description of the algorithms required to build the recoverable semantic structure, and discuss how the problem of infinite recursion can be handled when using relations in descriptions; and (/;') we show how the two levels of representation facilitate the generation of one‐anaphoric noun phrases.
Topical, temporal, and spatial constraints on linguistic realization
Authors: Maybury Mark T.
Published: April 2007

Previous work in natural language génération has exploited discourse focus to guide the selection of propositional content and the génération of referring expressions (e.g., pronominalization, définite noun phrase génération). However, there are many other sources of contextual information which can be used to constrain linguistic realization. The realization of certain classes of temporal and spatial référents, for example, can be guided by more detailed models of time and space. Therefore, this article first identifies a number of contextual coordinates or points of référence (known as indexicals in linguistics). Next, we formalize three of these contextual coordinates – topic, time, and space – in a computational model. In doing so, the article describes the use of a Reichenbachian temporal model which is exploited to guide the realization of verb tense and aspect as well as the realization of temporal référents (e.g., temporal connectives and adverbials such as “meanwhile” and “ten minutes later”). The article then describes a spatial model which is used to guide the linguistic realization of spatial référents (e.g., “here,”“there”) and spatial adverbials (e.g., “two miles away”). We discuss the relation between these temporal and spatial models and illustrate their use in generating text from two different application systems. We find that the combined use of topical, temporal, and spatial contextual coordinates enhances the fluency, connectivity, and conciseness of the resulting text.
Using meta‐comments to generate fluent text in a technical domain1
Authors: ZUKERMAN INGRID
Published: April 2007

Naturally occurring discourse often contains expressions such as “however,”“as I have stated before,” and “next.” These expressions, denoted meta‐comments, carry important information which helps a hearer speed up the comprehension process. In this paper, we present a mechanism for the generation of meta‐comments and their incorporation into computer‐generated discourse. This mechanism is based on a simple model of the anticipated effect of the messages to be conveyed and of the meta‐comments on the hearer's comprehension. It was implemented in a system called FIGMENT, which generates commentaries on the solution of algebraic equations.

Le discours naturel contient souvent des expressions comme 〈〈 cependant 〉〉 et 〈〈 comme je ľai dit auparavant 〉〉. Ces expressions, appelées méta‐commentaires, contiennent des informations importantes qui aident à accélérer le processus de compréhension de ľ auditeur. Dans cet article, ľ auteur présente un mécanisme de génération de métacommentaires et ? intégration de ceux‐ci au discours créé par ordinateur. Ce mécanisme est basé sur un modèle simple de ľeffet anticipé des messages devant ětre transmis et de ľ';effet des méta‐commentaires sur la compréhension de ľ auditeur. II a été mis en oeuvre dans un système appele FIGMENT, qui génère des commentaires sur la solution ?équations algébriques.
COMBINING KNOWLEDGE BASES CONSISTING OF FIRST‐ORDER THEORIES
Authors: Baral Chitta , Kraus Sarit , Minker Jack , Subrahmanian V. S.
Published: April 2007

Consider the construction of an expert system by encoding the knowledge of different experts. Suppose the knowledge provided by each expert is encoded into a knowledge base. Then the process ofcombiningthe knowledge of these different experts is an important and nontrivial problem. We study this problem here when the expert systems are considered to be first‐order theories. We present techniques for resolving inconsistencies in such knowledge bases. We also provide algorithms for implementing these techniques.
MULTIPLY SECTIONED BAYESIAN NETWORKS AND JUNCTION FORESTS FOR LARGE KNOWLEDGE‐BASED SYSTEMS
Authors: Xiang Yang , Poole David , Beddoes Michael P.
Published: April 2007

Bayesian networks provide a natural, concise knowledge representation method for building knowledge‐based systems under uncertainty. We consider domains representable by general but sparse networks and characterized by incremental evidence where the probabilistic knowledge can be captured once and used for multiple cases. Current Bayesian net representations do not consider structure in the domain and lump all variables into ahomogeneousnetwork. In practice, one often directs attention to only part of the network within a period of time; i.e., there is “localization” of queries and evidence. In such case, propagating evidence through a homogeneous network is inefficient since the entire network has to be updated each time. This paper derives reasonable constraints, which can often be easily satisfied, that enable a natural{localization preserving)partition of a domain and its representation by separate Bayesian subnets. The subnets are transformed into a set of permanent junction trees such that evidential reasoning takes place at only one of them at a time; and marginal probabilities obtained are identical to those that would be obtained from the homogeneous network. We show how to swap in a new junction tree, and absorb previously acquired evidence. Although the overall system can be large, computational requirements are governed by the size of one junction tree.
RESTRICTING THE WEAK‐GENERATIVE CAPACITY OF SYNCHRONOUS TREE‐ADJOINING GRAMMARS
Authors: Shieber Stuart M.
Published: April 2007

The formalism of synchronous tree‐adjoining grammars, a variant of standard tree‐adjoining grammars (TAG), was intended to allow the use of TAGs for language transduction in addition to language specification. In previous work, the definition of the transduction relation defined by a synchronous TAG was given by appeal to an iterative rewriting process. The rewriting definition of derivation is problematic in that it greatly extends the expressivity of the formalism and makes the design of parsing algorithms difficult if not impossible. We introduce a simple, natural definition of synchronous tree‐adjoining derivation, based on isomorphisms between standard tree‐adjoining derivations, that avoids the expressivity and implementability problems of the original rewriting definition. The decrease in expressivity, which would otherwise make the method unusable, is offset by the incorporation of an alternative definition of standard tree‐adjoining derivation, previously proposed for completely separate reasons, thereby making it practical to entertain using the natural definition of synchronous derivation. Nonetheless, some remaining problematic cases call for yel more flexibility in the definition; the isomorphism requirement may have to be relaxed. It remains for future research to rune the exact requirements on the allowable mappings.
EXTENSION OF THE RELATIONAL DATABASE AND ITS ALGEBRA WITH ROUGH SET TECHNIQUES
Authors: Beaubouef Theresa , Petry Frederick E. , Buckles Bill P.
Published: April 2007

This paper describes a database model based on the original rough sets theory. Its rough relations permit the representation of a rough set of tuples not definable in terms of the elementary classes, except through use of lower and upper approximations. The rough relational database model also incorporates indiscernibility in the representation and in all the operators of the rough relational algebra. This indiscernibility is based strictly on equivalence classes which must be defined for every attribute domain.

There are several obvious applications for which the rough relational database model can more accurately model an enterprise than does the standard relational model. These include systems involving ambiguous, imprecise, or uncertain data. Retrieval over mismatched domains caused by the merging of one or more applications can be facilitated by the use of indiscernibility, and naive system users can achieve greater recall with the rough relational database. In addition, applications inherently “rough” could be more easily implemented and maintained in the rough relational database.
INCREMENTAL CONCEPT FORMATION ALGORITHMS BASED ON GALOIS (CONCEPT) LATTICES
Authors: Godin Robert , Missaoui Rokia , Alaoui Hassan
Published: April 2007

The Galois (or concept) lattice produced from a binary relation has proved useful for many applications. Building the Galois lattice can be considered a conceptual clustering method because it results in a concept hierarchy. This article presents incremental algorithms for updating the Galois lattice and corresponding graph, resulting in an incremental concept formation method. Different strategies are considered based on a characterization of the modifications implied by such an update. Results of empirical tests are given in order to compare the performance of the incremental algorithms to three other batch algorithms. Surprisingly, when the total time for incremental generation is used, the simplest and less efficient variant of the incremental algorithms outperforms the batch algorithms in most cases. When only the incremental update time is used, the incremental algorithm outperforms all the batch algorithms. Empirical evidence shows that, on the average, the incremental update is done in time proportional to the number of instances previously treated. Although the worst case is exponential, when there is a fixed upper bound on the number of features related to an instance, which is usually the case in practical applications, the worst‐case analysis of the algorithm also shows linear growth with respect to the number of instances.
DATA‐BASED ACQUISITION AND INCREMENTAL MODIFICATION OF CLASSIFICATION RULES
Authors: Shan Ning , Ziarko Wojciech
Published: April 2007

One of the most important problems in the application of knowledge discovery systems is the identification and subsequent updating of rules. Many applications require that the classification rules be derived from data representing exemplar occurrences of data patterns belonging to different classes. The problem of identifying such rules in data has been researched within the field of machine learning, and more recently in the context of rough set theory and knowledge discovery in databases. In this paper we present an incremental methodology for finding all maximally generalized rules and for adaptive modification of them when new data become available. The methodology is developed in the context of rough set theory and is based on the earlier idea of discernibility matrix introduced by Skowron.
ON MODELING UNCERTAINTY WITH INTERVAL STRUCTURES
Authors: Wong S. K. M. , Wang L. S. , Yao Y Y.
Published: April 2007

In this paper, we introduce the notion of interval structures in an attempt to establish a unified framework for representing uncertain information. Two views are suggested for the interpretation of an interval structure. A typical example using thecompatibility viewis the rough set model in which the lower and upper approximations form an interval structure. Incidence calculus adopts theallocation viewin which an interval structure is defined by the tightest lower and upper incidence bounds. The relationship between interval structures and interval‐based numeric belief and plausibility functions is also examined. As an application of the proposed model, an algorithm is developed for computing the tightest incidence bounds.
ON COMPUTING THE MINIMAL LABELS IN TIME POINT ALGEBRA NETWORKS
Authors: Gerevini Alfonso , Schubert Lenhart
Published: April 2007

We analyze the problem of computing the minimal labels for a network of temporal relations in point algebra. Van Beek proposes an algorithm for accomplishing this task, which takes O(max(n3, n2 m)) time (for n points and m ≠‐relations). We show that the proof of the correctness of this algorithm given by van Beek and Cohen is faulty, and we provide a new proof showing that the algorithm is indeed correct.
PATTERN‐BASED LEARNING AND SPATIALLY ORIENTED CONCEPT FORMATION IN A MULTI‐AGENT, DECISION‐MAKING EXPERT
Authors: Epstein Susan L. , Gelfand Jack , Lesniak Joanna
Published: April 2007

As they gain expertise in problem solving, people increasingly rely on patterns and spatially oriented reasoning. This paper describes an associative visual‐pattern classifier and the automated acquisition of new, spatially oriented reasoning agents that simulate such behavior. They are incorporated into a multi‐agent game‐learning program whose architecture robustly combines agents with conflicting perspectives. When tested on three games, the visual‐pattern classifier learns meaningful patterns, and the pattern‐based, spatially oriented agents generalized from these patterns are generally correct. The accuracy of the contribution of each of the newly created agents to the decision‐making process is measured against an expert opponent, and a perceptron‐Iike algorithm is used to learn game‐specific weights for these agents. Much of the knowledge encapsulated by the new agents was previously inexpressible in the program's representation and in some cases is not readily deducible from the rules.
CONSTRAINED RESOLUTION AND ABDUCTTVE TEMPORAL REASONING
Authors: Chleq Nicolas
Published: April 2007

This article presents our work on the effective implementation of abduction in temporal reasoning. This works builds on some results, both in the logic programming field and in the automated reasoning area. We have defined and implemented an abductive procedure, which is well adapted for temporal reasoning because it is based on a constrained resolution principle. Constrained resolution has two advantages for temporal reasoning: First, it allows us to deal efficiently with temporal ordering and equality predicates, which are otherwise too much trouble with classical resolution; second, it allows a restricted form of abduction where hypotheses are limited to ordering relationships. From the logic programming area, our work uses results and procedures developed by others in the abductive logic programming field. The procedure we define and implement in this work is relatively independent of the temporal formalism: It has been used with some reified temporal logics and with the event calculus. More generally it can be used on any point‐based temporal formalism, provided that a correct and complete algorithm is available for checking the consistency of a set of temporal ordering relationships in this language.
NATURAL ADVANTAGE EFFECT, LOCATION AND TRADE PATTERNS IN INCREASING RETURNS TO SCALE INDUSTRIES
Authors: Alfredo Minerva Gaetano
Published: April 2007

In a two sectors, two regions economy I show that the higher the increasing returns to scale of an industry, the more easily it will concentrate in response to natural advantage (giving rise to what I call Natural Advantage Effect). To this end, one sector is assumed to be perfectly competitive and the other is monopolistically competitive, with a region's firms producing at a lower marginal cost than the others in the monopolistic sector (or equivalently producing varieties more intensely demanded by consumers). If capital is mobile between regions in the long run, I analytically characterize the process of industrial location of the imperfectly competitive sector in the region with the natural advantage.
DOES MIGRATION REDUCE REGIONAL DISPARITIES? THE ROLE OF SKILL‐SELECTIVE FLOWS
Authors: Fratesi Ugo , Riggi Massimiliano R.
Published: April 2007

The existence of income per capita disparities is a striking feature of European regional development, while increasing internal migration is often cited as a convergence factor. This paper states that this argument is too simple if migration concerns skilled workers. To support this statement, the focus is on skill‐selective migration flows: first, it is shown how easily they can happen (for instance, they can be caused by different regional wage settings); then, a model is used to investigate the effects of different regional endowments of immobile factors on migration. The model shows that skill‐selective migration can, in some cases, lead to increasing income per capita disparities and, for this reason, policy makers need to pay attention when attempting to narrow regional disparities by easing interregional migration.
THE DEVELOPMENT OF REGIONAL INTEGRATION IN EAST ASIA: FROM THE VIEWPOINT OF SPATIAL ECONOMICS
Authors: Fujita Masahisa
Published: April 2007

This paper examines the recent evolution of regional integration in East Asia, and discusses the prospects and tasks of further integration. After an overview of the globalization and regional integration trend in EU, NAFTA and East Asia during the past half‐century, we introduce the basic framework of spatial economics, often called the new economic geography. In terms of globalization and regional integration, it is important to examine the general effects of decreasing transport costs (broadly defined) on spatial distribution of economic activities. Given this theoretical framework, we examine the changing economic interdependency within East Asia, as well as that between East Asia and the rest of the world over the last three decades. Next, we focus on regional diversity and disparity in East Asia. Finally, we compare the regional integration in EU with that of East Asia, and examine the tasks and prospects of further promotion of East Asian integration.
Standard Distributions: One Graph Fits All
Authors: Wagner Clifford H.
Published: April 2007

Standard distributions are ubiquitous but not unique. With suitable scaling, the graph of a standard distribution serves as the graph for every distribution in the family. The standard exponential can easily be taught in elementary statistics courses.
Solubility of corundum + kyanite in H2O at 700°C and 10 kbar: evidence for Al‐Si complexing at high pressure and temperature
Authors: MANNING C. E.
Published: April 2007

The solubility of the assemblage corundum + kyanite in H2O was determined at 700°C and 10 kbar, using a piston‐cylinder apparatus and rapid‐quench/fluid‐extraction techniques. Weighted mean concentrations of total Al and Si were 5.80 ± 0.03 mmol kg−1 H2O and 0.308 ± 0.003 mol kg−1 H2O, respectively (1σ errors). The Al concentration is nearly five times higher than that of corundum solubility in pure H2O. This difference is interpreted to arise from complexing between Si and Al to form HAlSiO4,aq species. Charged or more polymerized species are also possible, but their abundance cannot be constrained based on these experiments. Assumption of a single aqueous aluminosilicate complex permits calculation of the thermodynamic consequences of Al‐Si interaction in high‐pressure fluids, as well as phase diagrams for the system Al‐Si‐O‐H. Formation of Al‐Si complexes leads to a large increase in dissolved Al with increasing Si in solution, such that Al concentration in equilibrium with kyanite + quartz is predicted to be 7.1 mmolal, higher than with kyanite + corundum. The elevated concentration of Si in deep‐crustal and mantle aqueous fluids suggests that Al must readily be dissolved and transported by Al‐Si complexing in high‐pressure metamorphic and metasomatic environments. The results provide a simple explanation for the common observation of kyanite + quartz segregations in eclogites and Barrovian metamorphic rocks.
Galectin‐4 is involved in p27‐mediated activation of the myelin basic protein promoter
Authors: Wei Qiou , Eviatar‐Ribak Tamar , Keith Miskimins W. , Miskimins Robin
Published: April 2007

Our previous studies have found that expression of p27 in oligodendrocytes enhances myelin basic protein (MBP) gene expression through a mechanism that involves the transcription factor Sp1. In this study we show that this activation only requires the N‐terminal 45 amino acids of p27 containing a functional cyclin‐binding motif. In an effort to identify other cofactors that are involved in the p27‐mediated activation of MBP gene expression, a yeast two‐hybrid assay was performed using an N‐terminal truncated p27 and a mouse embryo cDNA library. Galectin‐4 was found to interact with p27 in the yeast two‐hybrid assay. This novel interaction was also confirmed using a glutathione‐S‐transferase interaction assay and immunoprecipitation assays. Expression of galectin‐4 in primary oligodendrocytes was confirmed by western blot. Additionally, the MBP promoter could be activated by expression of galectin‐4 in CG4 oligodendrocytes, similar to the effects of increased p27 levels. We also show that Sp1 and galectin‐4 interact in cells, while a complex of all three proteins could not be found. We conclude that galectin‐4 is involved in the p27‐mediated activation of the MBP gene, possibly through modulation of the glycosylation status of the transcription factor Sp1.