Search

This paper describes a methodology for semiautomatic grammar induction from unannotated corpora of information-seeking queries in a restricted domain. The grammar contains both semantic and syntactic structures, which are conducive to (spoken) natural language understanding. Our work aims to ameliorate the reliance of grammar development on expert handcrafting or on the availability of annotated corpora. To strive for reasonable coverage on real data, as well as portability across domains and languages, we adopt a statistical approach. Agglomerative clustering using the symmetrized divergence criterion groups words 'spatially.' These words have similar left and right contexts and tend to form semantic classes. Agglomerative clustering using mutual information groups words 'temporally.' These words tend to co-occur sequentially to form phrases or multiword entities. Our approach is amenable to the optional injection of prior knowledge to catalyze grammar induction. The resultant grammar is interpretable by humans and is amenable to hand-editing for refinement. Hence, our approach is semiautomatic in nature. Experiments were conducted using the ATIS (Air Travel Information Service) corpus and the semiautomatically-induced grammar [G.sub.SA] is compared to an entirely handcrafted grammar [G.sub.H]. [G.sub.H] took two months to develop and gave concept error rates of 7 percent and 11.3 percent, respectively, in language understanding of two test corpora. [G.sub.SA] took only three days to produce and gave concept errors of 14 percent and 12.2 percent on the corresponding test corpora. These results provide a desirable trade-off between language understanding performance and grammar development effort. Index Terms--Grammar induction, semantic processing, natural language understanding, concepts extraction, knowledge acquisition.

Research devoted to developing knowledge-based tools for database design has demonstrated that it is possible to encode a great deal of process knowledge about database design in a (knowledge-based) computer program. However, experience with these tools shows that the contribution of an expert human designer extends beyond his or her knowledge of database design techniques. This paper discusses the application of an approach, called Naive Semantics (NS), to simulate the contributions made to a design based on the designer's general knowledge. Naive semantics involves the use of an extensible store of generally understood knowledge about the world. This paper describes the types of information that could be included in a Naive Semantics knowledge base and how that knowledge might be applied to increase the effectiveness of automated database design systems. Results of various implementations of ontologies based on Naive Semantics are discussed. Index Terms--Naive Semantics, database design, design automation, entity-relationship model.

We introduce a transformation system for concurrent constraint programming (CCP). We define suitable applicability conditions for the transformations that guarantee the input/output CCP semantics is also preserved when distinguishing deadlocked computations from successful ones and when considering intermediate results of (possibly) nonterminating computations. The system allows us to optimize CCP programs while preserving their intended meaning: In addition to the usual benefits for sequential declarative languages, the transformation of concurrent programs can also lead to the elimination of communication channels and of synchronization points, to the transformation of nondeterministic computations into deterministic ones, and to the crucial saving of computational space. Furthermore, since the transformation system preserves the deadlock behavior of programs, it can be used for proving deadlock-freeness of a given program with respect to a class of queries. To this aim, it is sometimes sufficient to apply our transformations and to specialize the resulting program with respect to the given queries in such a way that the obtained program is trivially deadlock-free. Categories and Subject Descriptors: D.3.2 [Programming Languages]: Language Classifications--concurrent, distributed, and parallel languages; I.2.2 [Artificial Intelligence]: Automatic Programming--Program transformation; F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages--algebraic approaches to semantics; D.1.3 [Programming Techniques]: Concurrent Programming General Terms: Languages, Theory Additional Key Words and Phrases: Concurrent constraint programming, deadlock-freeness, optimization

Several recent studies have introduced lightweight versions of Java: reduced languages in which complex features like threads and reflection are dropped to enable rigorous arguments about key properties such as type safety. We carry this process a step further, omitting almost all features of the full language (including interfaces and even assignment) to obtain a small calculus, Featherweight Java, for which rigorous proofs are not only possible but easy. Featherweight Java bears a similar relation to Java as the lambda-calculus does to languages such as ML and Haskell. It offers a similar computational "feel," providing classes, methods, fields, inheritance, and dynamic typecasts with a semantics closely following Java's. A proof of type safety for Featherweight Java thus illustrates many of the interesting features of a safety proof for the full language, while remaining pleasingly compact. The minimal syntax, typing rules, and operational semantics of Featherweight Java make it a handy tool for studying the consequences of extensions and variations. As an illustration of its utility in this regard, we extend Featherweight Java with generic classes in the style of GJ (Bracha, Odersky, Stoutamire, and Wadler) and give a detailed proof of type safety. The extended system formalizes for the first time some of the key features of GJ. Categories and Subject Descriptors: D.3.1 [Programming Languages]: Formal Definitions and Theory; D.3.2 [Programming Languages]: Language Classifications--Object-oriented languages; D.3.3 [Programming Languages]: Language Constructs and Features--Classes and objects; Polymorphism; F.3.3 [Logics and Meaning of Programs]: Studies of Program Constructs--Object-oriented constructs General Terms: Design, Languages, Theory Additional Key Words and Phrases: Compilation, generic classes, Java, language design, language semantics

We address the problem of providing a homogeneous framework for integrating, in a database environment, active rules, which allow the specification of actions to be executed whenever certain events take place, and deductive rules, which allow the specification of deductions in a logic programming style. Actually, it is widely recognized that both kinds of rules enhance the capabilities of database systems since they provide very natural mechanisms for the management of various important activities (e.g., knowledge representation, complex data manipulation, integrity constraint enforcement, view maintenance). However, in spite of their strong relationship, little work has been done on the unification of these powerful paradigms. In this paper, we present a rule-based language with an event-driven semantics that allows programmers to express both active and deductive computations. The language is based on a new notion of production rules whose effect is both a change of state and an answer to a query. By using several examples, we show that this simple language schema allows us to uniformly define different computations on data, including complex data manipulations, deductive evaluations, and active rule processing. We define the semantics of the language and then describe the architecture of a preliminary implementation of the language. Finally, we report about application and experience of use of the language. Index terms - Active databases, deductive databases, query languages, semantics of rule systems, integration of database languages, complex objects.

This paper presents a language of update programs that integrates logical queries, bulk updates and hypothetical reasoning in a seamless manner. There is no syntactic or semantic distinction between queries and updates. Update programs extend logic programs with negation in both syntax and semantics. They allow bulk updates in which an arbitrary update is applied simultaneously for all answers of an arbitrary query. Hypothetical reasoning is naturally supported by testing the success or failure of an update. We describe an alternating fixpoint semantics of update programs and show that it can express all nondeterministic database transformations. Index Terms - Bulk updates, hypothetical reasoning, logical queries, alternating fixpoint semantics, database languages.

The declarative primitives based decomposition abstraction enhances parallel execution in rule-based programming languages. The decomposition primitives construct indirect and direct relations among the data, and the rules under general object-based semantics. The semantic implementation allows a compile time detection of rule interference for concurrent execution of multiple instances. Decomposition abstraction takes care of synchronization and communication features and highlights the difficulties of granularity and scheduling.

A task-based specification technique for conceptual models uses conceptual graphs as the formalism to specify software requirements and capture rich semantics. The task structure of problem-solving knowledge provides the specification, which is then iteratively refined and verified. The conceptual graphs are preferred over other methods due to their ability to express both declarative and procedural knowledge. The assimilation capability of these graphs enables integration of specifications for different views under a single task. The graphs also allow sharing of artifacts of different models.

This research presents preliminary results generated from the semantic retrieval research component of the Illinois Digital Library Initiative (DLI) project. Using a variation of the automatic thesaurus generation techniques, to which we refer as the concept space approach, we aimed to create graphs of domain-specific concepts (terms) and their weighted co-occurrence relationships for all major engineering domains. Merging these concept spaces and providing traversal paths across different concept spaces could potentially help alleviate the vocabulary (difference) problem evident in large-scale information retrieval. We have experimented previously with such a technique for a smaller molecular biology domain (Worm Community System, with 10+ MBs of document collection) with encouraging results. In order to address the scalability issue related to large-scale information retrieval and analysis for the current Illinois DLI project, we recently conducted experiments using the concept space approach on parallel supercomputers. Our test collection included 2+ GBs of computer science and electrical engineering abstracts extracted from the INSPEC database. The concept space approach called for extensive textual and statistical analysis (a form of knowledge discovery) based on automatic indexing and co-occurrence analysis algorithms, both previously tested in the biology domain. Initial testing results using a 512-node CM-5 and a 16-processor SGI Power Challenge were promising. Power Challenge was later selected to create a comprehensive computer engineering concept space of about 270,000 terms and 4,000,000+ links using 24.5 hours of CPU time. Our system evaluation involving 12 knowledgeable subjects revealed that the automatically-created computer engineering concept space generated significantly higher concept recall than the human-generated INSPEC computer engineering thesaurus. However, the INSPEC was more precise than the automatic concept space. Our current work mainly involves creating concept spaces for other major engineering domains and developing robust graph matching and traversal algorithms for cross-domain, concept-based retrieval. Future work also will include generating individualized concept spaces for assisting user-specific concept-based information retrieval. Index Terms - Semantic retrieval, concept space, concept association, parallel computing, digital library.

The PPL framework is an extension of logic programming, with operational and declarative semantics, and is aimed at handling resources. The semantics extend the concepts of success set, instantaneous consequence operator and model. The extension incorporates the pre- and post-conditions that affect the resource terms and atoms to Horn clauses. The context helps to handle sequential and parallel composition parameters. Non-monotonic resource activities and context reliance problems are handled through traces. PPL is suitable for coding applications using databases, actions and changes.

This paper discusses a paradigm and prototype system for the design-time expression, checking, and automatic implementation of the semantics of database updates. Here, enforcement rules are viewed as the implementation of constraints and are specified, checked for consistency, and then finally mapped to object-oriented code during database design. A classification of enforcement rule types is provided as a basis for these design activities, and the general strategy for specification, analysis, and implementation of these rules within a semantic modeling paradigm is discussed. SORAC (semantic, objects, relationships, and constraints), a prototype database design system at the University of Rhode Island, is also described. Index Terms - Data modeling, database updates, constraint maintenance, schema checking, data consistency, active databases.

This paper defines principles for organizing semantic relations represented by slots in frame-structured knowledge bases. We organize slots based on the knowledge-level semantics of relations and the symbol-level function of slots that implement the representation language. The symbol-level organization of slots depends on the inferencing and expressive capabilities of the knowledge representation system. At the knowledge level, two entirely different organizational schemes are identified: one based on linguistic similarities and differences, and another based on the types of concepts being related. Index Terms - Semantic relations, slots, frame-based systems, classification of relations.

Mealy machines can more effectively solve the look-ahead problem caused by the longest-match rule in lexical analysis. Unlike Moore machines, which are the basis for traditional lexical analyzers, Mealy machines can solve the look-ahead problem without employing extra-automata devices. Mealy machines derived from generalized suffix automata can be used as the underlying data structure of the data-parallel lexical analysis algorithm since they do not require buffering and re-scanning.

A formal model of Smalltalk-80, an untyped object-oriented programming language possessing a dynamic method binding and an inheritance class hierarchy has been developed. The model provides a framework for rapid generation of an interpreter and for correctness proofs of the interpreter implementation. The copy-rule semantics and an integration of the operational and denotational semantics are discussed.

Techniques for the development of reliable information systems on the basis of their formal specification are the main concern in our project. Our work focuses on the specification language TROLL light which allows to describe the part of the world to be modeled as a community of concurrently existing and communicating objects. Our specification language comes along with an integrated, open development environment. The task of this environment is to give support for the creation of correct information systems. Two important ingredients of the environment to be described here in more detail are the animator and the proof support system. Index Terms - Information system design, semantic data model, object specification, certification, validation, verification.

A research study in programming languages introduced a powerful, low-level software debugging language called GDL. The debugging language has primitives that include the intuitive and formal semantics of imperative debugging. GDL's ability to incorporate higher-level constructs has led to its use in analyzing key semantic issues that designers and debugging language implementors have to contend with. The efficiency of different GDL constructs on typical architectures are evaluated. The semantic issues that result from such an integration are also discussed.

Databases and knowledge bases could be inconsistent in many ways. For example, during the construction of an expert system, we may consult many different experts. Each expert may provide us with a group of rules and facts which are self-consistent. However, when we coalesce the facts and rules provided by these different experts, inconsistency may arise. Alternatively, knowledge bases may be inconsistent due to the presence of some erroneous information. Thus, a framework for reasoning about knowledge bases that contain inconsistent information is necessary. Such a framework was described in [1], [21]. However, existing frameworks for reasoning with inconsistency do not support reasoning by cases and reasoning with the law of excluded middle ('everything is either true or false'). In this paper, we show how reasoning with cases, and reasoning with the law of excluded middle may be captured. We develop a declarative and operational semantics for knowledge bases that are possibly inconsistent. We compare and contrast our work with work on explicit and non-monotonic modes of negation in logic programs and suggest under what circumstances one framework may be preferred over another. Index Terms - Logic programming, deductive databases, reasoning with inconsistency, nonmonotonic negation.

This paper presents an application of the concepts of siphons (deadlocks) and inhibitor arcs in Petri net theory to logic programs with negations. More specifically, an extended Petri net is used to model function-free normal logic programs. In this model, because of the presence of inhibitor arcs, the arbitrary applications of firing rule may cause a contradictory situation. We suggest two directions to avoid contradictions: greedy and secure applications of firing rule. We choose the secure application in this paper and show that this is a direct translation of the well-founded semantics in the net model. Furthermore, we show that the greatest unfounded set corresponds to the greatest siphon in Petri net theory when we delete the transitions disabled by the secure application of firing rule, and that the property of siphon simplifies the computation of well-founded semantics for logic programs. We also propose the reduced-Petri-net method by which we can reduce an extended Petri net to a Petri net without inhibitor arcs and compute the well-founded model by iterative applications of this transformation using conventional application of firing rule. Index Terms - Logic programming, inhibitor arcs, negations, normal logic programs, Petri nets, siphons (deadlocks), well-founded semantics.

We give in this paper a sufficient condition under which the least fixpoint of the equation X = a + f(X)X equals the least fixpoint of the equation X = a + f(a)X. We then apply that condition to recursive logic programs containing chain rules: we translate it into a sufficient condition under which a recursive logic program containing n [is greater than or equal to] 2 recursive calls in the bodies of the rules is equivalent to a linear program containing at most one recursive call in the bodies of the rules. We conclude with a discussion comparing our condition with the other approaches to linearization studied in the literature. Index Terms - Datalog program, chain rule program, linear program, fixpoint, semantics, rational languages and functions, linearization.

A standard relation has two dimensions: attributes and tuples. A temporal relation contains two additional orthogonal time dimensions, namely, valid time and transaction time. Valid time records when facts are true in the modeled reality, and transaction time records when facts are stored in the temporal relation. Although, in general, there are no restrictions between the valid time and transaction time associated with each fact, in many practical applications, the valid and transaction times exhibit more or less restricted interrelationships that define several types of specialized temporal relations. The paper examines five different areas where a variety of types of specialized temporal relations are present. In application systems with multiple, interconnected temporal relations, multiple time dimensions may be associated with facts as they flow from one temporal relation to another. For example, a fact may have an associated transaction time indicating when it was stored in a previous temporal relation. The paper investigates several aspects of the resulting generalized temporal relations, including the ability to query a predecessor relation from a successor relation. The presented framework for generalization and specialization allows researchers as well as database and system designers to precisely characterize, compare, and thus better understand temporal relations and the application systems in which they are embedded. The framework's comprehensiveness and its use in understanding temporal relations are demonstrated by placing previously proposed temporal data models within the framework. The practical relevance of the defined specializations and generalizations is illustrated by sample realistic applications in which they occur. The additional semantics of specialized relations are especially useful for improving the performance of query processing. Index Terms - Query processing, specialized temporal relations, generalized temporal relations, taxonomy, time attributes, temporal database, temporal semantics, transaction time, valid time