Faculty Projects

With today's software being written in a more component-based fashion (realized in architectures such as dynamic link libraries, CORBA and COM components, and others), the opportunity exists to improve the reliability of systems when they are upgraded. By reliability here, we mean that the working functionality of the current system should not be broken. We are looking into methods for specifying the differences between an upgraded and existing component, and at how these methods could be efficiently implemented to provide a highly reliable system, even during and after an upgrade. We have a rough prototype that is being used to understand and make concrete our ideas. Projects that will soon be ready to be pursued include extending the Linux dynamic library loader with ideas from this research, integrating these same ideas into the CORBA distributed object framework, parallelizing the frameworks, and more.

Graphical representations have many benefits over pure text, and conceptual graph formalization is a way of doing logic in diagrams. Our focus is in three areas: Efficient implementation of storage and retrieval The visual notation of conceptual graphs leads to obvious machine representations as bi-partite graph structures. The operations on conceptual graphs, such as join and project then can be implemented as graph algorithms. Our solution to making these operations efficient involve use of hash tables to give constant-time access and optimized algorithms for graph manipulations. We have also investigated the use of data parallel algorithms where the granularity level is given by the graph node itself. Representation of procedural knowledge Representation of procedures has always been a problem for knowledge representation systems. Our work preserves the visual character of the conceptual graph while allowing representation of processes through a consistent modification to the basic idea. The modification also preserves the declarative semantics of the graph while allowing an additional interpretation as a program involving changes of state.

This interactive system converts hand-written music scores to standard MIDI. The system relies on path traversal of stroked shapes and shape grammars for recognition (Keywords: handwritten, score, pattern recognition, MIDI, computer music).

It is known that two-way (deterministic or nondeterministic) finite automata accept only regular languages. That is, two-way finite automata do not accept more languages than one-way finite automata. However, two-way finite automata may accept the same regular languages using many fewer states than one-way finite automata. In this study, we focus on the tradeoff in the descriptional complexity between two-way deterministic finite automata and one-way nondeterministic finite automata. It has been shown that this problem is closely related to the open problem in complexity theory of whether deterministic logarithmic space (LOG) is properly contained in nondeterministic logarithmic space (NLOG).

We study a measure of nondeterminism in pushdown automata. Our measure is similar to the way nondeteminism are measured in Turing machines. We consider the question of what kinds of nondeterministic behaviors are feasible for pushdown automata and counter machines. We also attempt to classify context-free languages according to the amount of nondeterminism needed for the languages to be accepted by pushdown automata.

Visual programming is particularly well-suited for robotics applications, since the data used by robots has very intuitive visual representations. Altaira is a rule-based language for reactive robot control, using a subsumption architecture. On each execution cycle the robots sensors are sampled, and the combination of the sensor state and the robot's current knowledge of its environment are used to select a rule which may change the robot's actuators, the state, or both. Altaira was a finalist in the 1997 Visual Programming Challenge, held at the IEEE Symposium on Visual Languages in Capri, Italy in September 1997.

Geometry has used a visual notation for millenia. It seems reasonable to suppose that a visual programming language would be an effective way to express geometric reasoning, as would be used by a mobile robot. Isaac provides a notation for programming reactive mobile robot control algorithms by defining rules in a visual language. Sensor inputs arrive asynchronously, and cause objects to be added to the robot's world model. Rules are enabled by the intersection of the objects in the left hand side of the rule with objects in the world model model; the extent to which a rule is enabled is determined by the area of the intersection. Rule firings can add objects to the model, remove them from the model, or move them in the model. Actuator rules cause output to the robot's actuators when fired.

Revision programming is a knowledge representation formalism for describing constraints on databases, knowledge bases, and belief sets, and providing a computational mechanism to enforce them. Constraints are represented by sets of revision rules. Justified revisions semantics assigns to any initial database a set (possibly empty) of revisions. Each revision satisfies the constraints and differs minimally from initial database. The theoretical part of the research focuses on properties of revision programming, comparison with other formalisms, and annotated revision programs. The practical part includes implementation of a solver to compute justified revisions.

In this project we are building a parallel Prolog system that will permit parallel execution of Prolog programs on shared memory multiprocessors (such as Sequent Symmetry, Sun Sparc Multiprocessors, etc.) without any programmer intervention. To date, a parallel system called ACE that efficiently exploits both "and" and "or" parallelism has been completed. ACE has shown impressive results on a variety of applications written in Prolog. Work is in progress to optimize and extend this implementation further so that maximum efficiency and speed-ups are achieved. Implementations of parallel logic programming systems on distributed memory systems (Intel iPSC860) as well as distributed shared memory systems (KSR) are also being developed. We are also working in developing parallel computer architectures best suited for parallel execution of logic programs. Suitability of our implementation techniques to concurrent constraint languages is also being investigated.

In this project we are exploring and developing advanced programming paradigms dedicated to supporting applications for WWW. Current approaches to developing applications interacting with the Internet are highly ad-hoc and require deep knowledge of various communication protocols. We are proposing a programming framework, based on a logic-language, embedding a variety of features which will allow a uniform and high-level development of WWW-related applications. Various advanced forms of interaction with Internet are supported (active pages, meta-level programming, intelligent clients, intelligent servers, etc.).

Virtually all the informal and formal languages for problem description include the concept of Set. Nevertheless there are virtually no programming languages which embedds a sound notion of set . This is mainly related to the high complexity of efficiently manipulating sets. Recent results on computable fragments of set theory are suggesting the existence of specialized classes of sets and set operations which can be effectively implemented. The purpose of this research is to study this computable fragment and develop effective ways of embedding sets in traditional programming frameworks. We have already exposed various constraint-based mechanisms to effectively manipulate hereditarily-finite sets, integrating them within a logic-based language.

In this project we propose a practical framework for the encoding of semantic specifications of languages. Specifications are developed following the style of denotational semantics and are encoded using Horn clause logic. This automatically provides a logic theory representing the semantic specification, which can be used to perform reasoning, verification, and validation. We have demonstrated the flexibility of this methodology in the construction of semantic data filters to improve interoperability between software tools and in the development of Domain Specific Languages.

This project investigate the underlying computational complexity of some of the basic problems present in execution models of various class of declarative languages (e.g. logic programming). These results are used in deriving efficient, possibly optimal, data structures to solve this problem and to provide a formal framework for the comparison of existing execution mechanisms proposed in the literature to implement existing languages.

This research project aims at investigating and understanding the reasons behind widely different behavior of NP-Optimization problems with respect to efficient computation of optimal and approximately optimal solutions via algorithms and heuristics. The focus of the first part of the project is to identify and develop general criteria that will be useful in pinpointing the exact complexity of computing approximately optimal solutions to NP- Optimization problems. The objective here is to isolate the crucial ideas that are spread over a rich but diverse literature on the subject and develop a framework where all these results can be stated in a uniform fashion. Then they can be used for obtaining new results. The second part of the project addresses the complexity of solving problems via heuristics. The major portion of this work concentrates on understanding incremental heuristics. In particular, the research aims at making precise and quantifying the usefulness of a new solution to a heuristic in making progress towards computing an optimal or near-optimal solution. We envision that this research will result in a deeper understanding of the perplexing nature of the NP-Optimization problems.

The goal of this project is to understand when, where and how randomization is useful in the design of algorithms. The project also aims at developing techniques for analysing randomized algorithms. In a recent work, we have applied the notion of negative association to establish some probabilistic inequalities useful for analysis of certain randomized algorithms.

In this project we develop a high level action description language for representing and reasoning about actions in real-life domains in which actions have duration and delayed effects. The salient features of this language include an English-like syntax and an automata-based semantics. The former allows domain experts to use the language in specifying their domains of interest without having to deal with first-order logic languages while the latter provides an independent means for the verification of properties of systems under consideration. To compute the semantics of action theories, we will develop a logic programming system capable of predicting the consequences of actions as well as generating a sequence of actions that change the world from a state to a state. This system will be used in developing diagnostic agents, planning agents, agends for Web service composition, navigational agents for visually-impaired users, etc.

The objective of this project is to develop computer games that will teach basic Computer Science concepts in a fun, engaging, efficient, and effective way. The current game platforms being used are Microsoft XNA (XBOX), Nintendo DS, OpenSceneGraph, the Torque Game Engine, Alice (Carnegie Mellon University), and GameMaker.