The University of Texas at Austin

Doctoral Dissertations

TR-14-12

Austin Waters(1). "Infinite-Word Topic Models for Digital Media". The University of Texas at Austin, Department of Computer Science(1). Report# TR-14-12 (dissertation). October 10th, 2014.

NO ABSTRACT

DOWNLOAD NOT AVAILABLE

TR-14-07

Jacob Benoid Schrum(1). "Evolving Multimodal Behavior Through Modular Multiobjective Neuroevolution". The University of Texas at Austin, Department of Computer Science(1). Report# TR-14-07 (dissertation). May 1st, 2014. 208 pages.

Intelligent organisms do not simply perform one task, but exhibit multiple distinct modes of behavior. For instance, humans can swim, climb, write, solve problems, and play sports. To be fully autonomous and robust, it would be advantageous for artificial agents, both in physical and virtual worlds, to exhibit a similar diversity of behaviors. This dissertation develops methods for discovering such behavior automatically using multiobjective neuroevolution. First, sensors are designed to allow multiple different interpretations of objects in the environment (such as predator or prey). Second, evolving networks are given ways of representing multiple policies explicitly via modular architectures. Third, the set of objectives is dynamically adjusted in order to lead the population towards the most promising areas of the search space. These methods are evaluated in five domains that provide examples of three different types of task divisions. Isolated tasks are separate from each other, but a single agent must solve each of them. Interleaved tasks are distinct, but switch back and forth within a single evaluation. Blended tasks do not have clear barriers, because an agent may have to perform multiple behaviors at the same time, or learn when to switch between opposing behaviors. The most challenging of the domains is Ms. Pac-Man, a popular classic arcade game with blended tasks. Methods for developing multimodal behavior are shown to achieve scores superior to other Ms. Pac-Man results previously published in the literature. These results demonstrate that complex multimodal behavior can be evolved automatically, resulting in robust and intelligent agents.

DOWNLOAD TR-2170.pdf

TR-13-09

Edmund L. Wong(1). "Raising the BAR in Dependable Cooperative Services". The University of Texas at Austin, Department of Computer Science(1). Report# TR-13-09 (dissertation). April 23rd, 2013.

NO ABSTRACT

DOWNLOAD NOT AVAILABLE

TR-12-32

Todd Hester(1). "TEXPLORE: Temporal Difference Reinforcement Learning for Robots and Time-Constrained Domains". The University of Texas at Austin, Department of Computer Science(1). Report# TR-12-32 (dissertation). December 6th, 2012. 281 pages.

Robots have the potential to solve many problems in society, because of their ability to work in dangerous places doing necessary jobs that no one wants or is able to do. One barrier to their widespread deployment is that they are mainly limited to tasks where it is possible to hand-program behaviors for every situation that may be encountered. For robots to meet their potential, they need methods that enable them to learn and adapt to novel situations that they were not programmed for. Reinforcement learning (RL) is a paradigm for learning sequential decision making processes that could solve the problems of learning and adaptation on robots. This thesis identifies four key challenges that must be addressed for an RL algorithm to be practical for robotic control tasks. These RL for Robotics Challenges are: 1) it must learn in very few samples; 2) it must learn in domains with continuous state features; 3) it must handle sensor and/or actuator delays; and 4) it should continually take actions in real-time. This thesis focuses on addressing all four of these challenges. In particular, this thesis is focused on time-constrained domains where the first challenge is critically important. In these domains, the agent’s lifetime is not long enough for it to explore the domain thoroughly, and it must learn in very few samples. Although existing RL algorithms successfully address one or more of the RL for Robotics Challenges, no prior algorithm addresses all four of them. To fill this gap, this thesis introduces TEXPLORE, the first algorithm to address all four challenges. TEXPLORE is a model-based RL method that learns a random forest model of the domain which generalizes dynamics to unseen states. Each tree in the random forest model represents a hypothesis of the domain’s true dynamics, and the agent uses these hypotheses to explores states that are promising for the final policy, while ignoring states that do not appear promising. With sample-based planning and a novel parallel architecture, TEXPLORE can select actions continually in real-time whenever necessary. We empirically evaluate each component of TEXPLORE in comparison with other state-of-the-art approaches. In addition, we present modifications of TEXPLORE’s exploration mechanism for different types of domains. The key result of this thesis is a demonstration of TEXPLORE learning to control the velocity of an autonomous vehicle on-line, in real-time, while running on-board the robot. After controlling the vehicle for only two minutes, TEXPLORE is able to learn to move the pedals of the vehicle to drive at the desired velocities. The work presented in this thesis represents an important step towards applying RL to robotics and enabling robots to perform more tasks in society. By enabling robots to learn in few actions while acting on-line in real-time on robots with continuous state and actuator delays, TEXPLORE significantly broadens the applicability of RL to robots.

DOWNLOAD TR-2110.pdf

TR-12-22

W. Bradley Knox(1). "Learning from Human-Generated Reward". The University of Texas at Austin, Department of Computer Science(1). Report# TR-12-22 (dissertation). September 1st, 2012. 263 pages.

Robots and other computational agents are increasingly becoming part of our daily lives. They will need to be able to learn to perform new tasks, adapt to novel situations, and understand what is wanted by their human users, most of whom will not have programming skills. To achieve these ends, agents must learn from humans using methods of communication that are naturally accessible to everyone. This thesis presents and formalizes interactive shaping, one such teaching method, where agents learn from real-valued reward signals that are generated by a human trainer. In interactive shaping, a human trainer observes an agent behaving in a task environment and delivers feedback signals. These signals are mapped to numeric values, which are used by the agent to specify correct behavior. A solution to the problem of interactive shaping maps human reward to some objective such that maximizing that objective generally leads to the behavior that the trainer desires. Interactive shaping addresses the aforementioned needs of real-world agents. This teaching method allows human users to quickly teach agents the specific behaviors that they desire. Further, humans can shape agents without needing programming skills or even detailed knowledge of how to perform the task themselves. In contrast, algorithms that learn autonomously from only a pre-programmed evaluative signal often learn slowly, which is unacceptable for some real-world tasks with real-world costs. These autonomous algorithms additionally have an inflexibly defined set of optimal behaviors, changeable only through additional programming. Through interactive shaping, human users can (1) specify and teach desired behavior and (2) share task knowledge when correct behavior is already indirectly specified by an objective function. Additionally, computational agents that can be taught interactively by humans provide a unique opportunity to study how humans teach in a highly controlled setting, in which the computer agent's behavior is parametrized. This thesis answers the following question. How and to what extent can agents harness the information contained in human-generated signals of reward to learn sequential decision-making tasks? The contributions of this thesis begin with an operational definition of the problem of interactive shaping. Next, I introduce the TAMER framework, one solution to the problem of interactive shaping, and describe and analyze algorithmic implementations of the framework within multiple domains. This thesis also proposes and empirically examines algorithms for learning from both human reward and a pre-programmed reward function within an MDP, demonstrating two techniques that consistently outperform learning from either feedback signal alone. Subsequently, the thesis shifts its focus from the agent to the trainer, describing two psychological studies in which the trainer is manipulated by either changing their perceived role or by having the agent intentionally misbehave at specific times; we examine the effect of these manipulations on trainer behavior and the agent's learned task performance. Lastly, I return to the problem of interactive shaping, for which we examine a space of mappings from human reward to objective functions, where mappings differ by how much the agent discounts reward it expects to receive in the future. Through this investigation, a deep relationship is identified between discounting, the level of positivity in human reward, and training success. Specific constraints of human reward are identified (i.e., the "positive circuits" problem), as are strategies for overcoming these constraints, pointing towards interactive shaping methods that are more effective than the already successful TAMER framework.

DOWNLOAD TR-2098.pdf

TR-12-19

Doran Chakraborty(1). "Sample Efficient Multiagent Learning in the Presence of Markovian Agents". The University of Texas at Austin, Department of Computer Science(1). Report# TR-12-19 (dissertation). August 22nd, 2012. 256 pages.

The problem of multiagent learning (or MAL) is concerned with the study of how agents can learn and adapt in the presence of other agents that are simultaneously adapting. The problem is often studied in the stylized settings provided by repeated matrix games. The goal of this thesis is to develop MAL algorithms for such a setting that achieve a new set of objectives which have not been previously achieved. The thesis makes three main contributions. The first main contribution proposes a novel MAL algorithm, called Convergence with Model Learning and Safety (or CMLeS), that is the first to achieve the following three objectives: (1) converges to following a Nash equilibrium joint-policy in self-play; (2) achieves close to the best response when interacting with a set of memory-bounded agents whose memory size is upper bounded by a known value; and (3) ensures an individual return that is very close to its security value when interacting with any other set of agents. The second main contribution proposes another novel MAL algorithm that models a significantly more complex class of agent behavior called Markovian agents, that subsumes the class of memory-bounded agents. Called Joint Optimization against Markovian Agents (or Joma), it achieves the following two objectives: (1) achieves a joint-return very close to the social welfare maximizing joint-return when interacting with Markovian agents; (2) ensures an individual return that is very close to its security value when interacting with any other set of agents. Finally, the third main contribution shows how a key subroutine of Joma can be extended to solve a broader class of problems pertaining to Reinforcement Learning, called "Structure Learning in factored state MDPs". All of the algorithms presented in this thesis are well backed with rigorous theoretical analysis, including an analysis on sample complexity wherever applicable, as well as representative empirical tests.

DOWNLOAD TR-2095.pdf

TR-12-11

Alan J Lockett(1). "General-Purpose Optimization Through Information-Maximization". The University of Texas at Austin, Department of Computer Science(1). Report# TR-12-11 (dissertation). May 11th, 2012. 482 pages.

The primary goal of artificial intelligence research is to develop a machine capable of learning to solve disparate real-world tasks autonomously, without relying on specialized problem-specific inputs. This dissertation suggests that such machines are realistic: If No Free Lunch theorems were to apply to all real-world problems, then the world would be utterly unpredictable. In response, the dissertation proposes the information-maximization principle, which claims that the optimal optimization methods make the best use of the information available to them. This principle results in a new algorithm, evolutionary annealing, which is shown to perform well especially in challenging problems with irregular structure.

DOWNLOAD TR-2081.pdf

TR-12-05

Bryan Silverthorn(1). "A Probabilistic Architecture for Algorithm Portfolios". The University of Texas at Austin, Department of Computer Science(1). Report# TR-12-05 (dissertation). March 27th, 2012.

NO ABSTRACT

DOWNLOAD NOT AVAILABLE

TR-11-41

Shivaram Kalyanakrishnan(1). "Learning Methods for Sequential Decision Making with Imperfect Representations". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-11-41 (dissertation). December 1st, 2011. 346 pages.

Sequential decision making from experience, or reinforcement learning (RL), is a paradigm that is well-suited for agents seeking to optimize long-term gain as they carry out sensing, decision, and action in an unknown environment. RL tasks are commonly formulated as Markov Decision Problems (MDPs). Learning in finite MDPs enjoys several desirable properties, such as convergence, sample-efficiency, and the ability to realize optimal behavior. Key to achieving these properties is access to a perfect representation, under which the state and action sets of the MDP can be enumerated. Unfortunately, RL tasks encountered in the real world commonly suffer from state aliasing, and nearly always they demand generalization. As a consequence, learning in practice invariably amounts to learning with imperfect representations. In this dissertation, we examine the effect of imperfect representations on different classes of learning methods, and introduce techniques to improve their practical performance. We make four main contributions. First we introduce ``parameterized learning problems'', a novel experimental methodology facilitating the systematic control of representational aspects such as state aliasing and generalization. Applying this methodology, we compare the class of on-line value function-based (VF) methods with the class of policy search (PS) methods. Results indicate clear patterns in the effects of representation on these classes of methods. Our second contribution is a deeper analysis of the limits imposed by representations on VF methods; specifically we provide a plausible explanation for the relatively poor performance of these methods on Tetris, the popular video game. The third major contribution of this dissertation is a formal study of the ``subset selection'' problem in multi-armed bandits. This problem, which directly affects the sample-efficiency of several commonly-used PS methods, also finds application in areas as diverse as industrial engineering and on-line advertising. We present new algorithms for subset selection and bound their performance under different evaluation criteria. Under a PAC setting, our sample complexity bounds indeed improve upon existing ones. As its fourth contribution, this dissertation introduces two hybrid learning architectures for combining the strengths of VF and PS methods. Under one architecture, these methods are applied in sequence; under the other, they are applied to separate components of a compound task. We demonstrate the effectiveness of these methods on a complex simulation of robot soccer. In sum, this dissertation makes philosophical, analytical, and methodological contributions towards the development of robust and automated learning methods for sequential decision making with imperfect representations.

DOWNLOAD TR-2063.pdf

TR-11-40

Juhyun Lee(1). "Robust Color-based Vision for Mobile Robots". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-11-40 (dissertation). November 30th, 2011. 153 pages.

An intelligent agent operating in the real world needs to be fully aware of the surrounding environment to make the best decision possible at any given point of time. There are many forms of input devices for a robot that gather real-time information of the surroundings, such as video cameras, laser/sonar range finders, and GPS to name a few. In this thesis, a vision system for a mobile robot navigating through different illumination conditions is investigated. Many state-of-the-art object recognition algorithms employ methods running on grayscale images, because using color is difficult for several reasons: (a) The object-of-interest's true colors may not be recorded by the camera hardware due to illumination artifacts, and (b) colors are often too ambiguous to be a robust visual descriptor of an object. In this dissertation, we address these two challenges and present new color-based vision algorithms for mobile robots that are robust and efficient. The first part of this dissertation focuses on the problem of color constancy for mobile robots under different lighting conditions. Specifically, We use a generate-and-test methodology to evaluate which simulated global illumination condition leads to the generated view that most closely matches what the robot actually sees. We assume the diagonal color model when generating views of the object of interest under previously unseen conditions. In the second part of the dissertation, we present a vision framework for mobile robots that enables observation of illumination artifacts in a scene and reasoning about the lighting conditions to achieve robust color-based object tracking. Before implementing this framework, we first devise a novel vision-based localization correction algorithm with graphics hardware support, and present how to find possibly shaded regions in the recorded scene by using techniques from 3D computer graphics. We then demonstrate how to integrate a color-based object tracker from the first part of this dissertation with our vision framework. Even with the contributions from the first two parts of the dissertation, there remains some degree of uncertainty in robot's assessment of an object's true color. The final part of this dissertation introduces a novel algorithm to overcome this uncertainty in color-based object tracking. We show how an agent can achieve robust color-based object tracking by combining multiple different visual characteristics of an object for more accurate robot vision in the real world.

DOWNLOAD TR-2062.pdf

TR-11-29

Ben Wiedermann(1). "Integrating Programming Languages and Databases via Program Analysis and Language Design". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-11-29 (dissertation). June 29th, 2011. 186 pages.

Researchers and practitioners alike have long sought to integrate programming languages and databases. Today's integration solutions focus on the data-types of the two domains, but today's programs lack transparency. A transparently persistent program operates over all objects in a uniform manner, regardless of whether those objects reside in memory or in a database. Transparency increases modularity and lowers the barrier of adoption in industry. Unfortunately, fully transparent programs perform so poorly that no one writes them. The goal of this dissertation is to increase the performance of these programs to make transparent persistence a viable programming paradigm. This dissertation contributes two novel techniques that integrate programming languages and databases. Our first contribution -- called query extraction -- is based purely on program analysis. Query extraction analyzes a transparent, object-oriented program that retrieves and filters collections of objects. Some of these objects may be persistent, in which case the program contains implicit queries of persistent data. Our interprocedural program analysis extracts these queries from the program, translates them to explicit queries, and transforms the transparent program into an equivalent one that contains the explicit queries. Query extraction enables programmers to write programs in a familiar, modular style and to rely on the compiler to transform their program into one that performs well. Our second contribution -- called RBI-DB+ -- is an extension of a new programming language construct called a batch block. A batch block provides a syntactic barrier around transparent code. It also provides a latency guarantee: If the batch block compiles, then the code that appears in it requires only one client-server communication trip. Researchers previously have proposed batch blocks for databases. However, batch blocks cannot be modularized or composed, and database batch blocks do not permit programmers to modify persistent data. We extend database batch blocks to address these concerns and formalize the results. Today's technologies integrate the data-types of programming languages and databases, but they discourage programmers from using procedural abstraction. Our contributions restore procedural abstraction's use in enterprise applications, without sacrificing performance. We argue that industry should combine our contributions with data-type integration. The result would be a robust, practical integration of programming languages and databases.

DOWNLOAD TR-2044.pdf

TR-11-26

David Pardoe(1). "Adaptive Trading Agent Strategies Using Market Experience". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-11-26 (dissertation). May 16th, 2011. 348 pages.

Along with the growth of electronic commerce has come an interest in developing autonomous trading agents. Often, such agents must interact directly with other market participants, and so the behavior of these participants must be taken into account when designing agent strategies. One common approach is to build a model of the market, but this approach requires the use of historical market data, which may not always be available. This dissertation addresses such a case: that of an agent entering a new market in which it has no previous experience. While the agent could adapt by learning about the behavior of other market participants, it would need to do so in an online fashion. The agent would not necessarily have to learn from scratch, however. If the agent had previous experience in similar markets, it could use this experience to tailor its learning approach to its particular situation. This dissertation explores methods that a trading agent could use to take advantage of previous market experience when adapting to a new market. Two distinct learning settings are considered. In the first, an agent acting as an auctioneer must adapt the parameters of an auction mechanism in response to bidder behavior, and a reinforcement learning approach is used. The second setting concerns agents that must adapt to the behavior of competitors in two scenarios from the Trading Agent Competition: supply chain management and ad auctions. Here, the agents use supervised learning to model the market. In both settings, methods of adaptation can be divided into four general categories: i) identifying the most similar previously encountered market, ii) learning from the current market only, iii) learning from the current market but using previous experience to tune the learning algorithm, and iv) learning from both the current and previous markets. The first contribution of this dissertation is the introduction and experimental validation of a number of novel algorithms for market adaptation fitting these categories. The second contribution is an exploration of the degree to which the quantity and nature of market experience impact the relative performance of methods from these categories.

DOWNLOAD TR-2041.pdf

TR-11-11

Uli Grasemann(1). "A Computational Model of Language Pathology in Schizophrenia". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-11-11 (dissertation). March 17th, 2011. 147 pages.

No current laboratory test can reliably identify patients with schizophrenia. Instead, key symptoms are observed via language, including derailment, where patients cannot follow a coherent storyline, and delusions, where false beliefs are repeated as fact. Brain processes underlying these and other symptoms remain unclear, and characterizing them would greatly enhance our understanding of schizophrenia. In this situation, computational models can be valuable tools to formulate testable hypotheses and to complement clinical research. This dissertation aims to capture the link between biology and schizophrenic symptoms using DISCERN, a connectionist model of human story processing. Competing illness mechanisms proposed to underlie schizophrenia are simulated in DISCERN, and are evaluated at the level of narrative language, the same level used to diagnose patients. The result is the first simulation of a speaker with schizophrenia. Of all illness models, hyperlearning, a model of overly intense memory consolidation, produced the best fit to patient data, as well as compelling models of delusions and derailments. If validated experimentally, the hyperlearning hypothesis could advance the current understanding of schizophrenia, and provide a platform for simulating the effects of future treatments.

DOWNLOAD TR-2024.pdf

TR-11-10

Allen Clement(1). "UpRight Fault Tolerance". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-11-10 (dissertation). March 15th, 2011. 235 pages.

Experiences with computer systems indicate an inconvenient truth: computers fail and they fail in interesting ways. Although using redundancy to protect against fail- stop failures is common practice, non-fail-stop computer and network failures occur for a variety of reasons including power outage, disk or memory corruption, NIC malfunction, user error, operating system and application bugs or misconfiguration, and many others. The impact of these failures can be dramatic, ranging from service unavailability to stranding airplane passengers on the runway to companies closing. While high-stakes embedded systems have embraced Byzantine fault tolerant techniques, general purpose computing continues to rely on techniques that are fundamentally crash tolerant. In a general purpose environment, the current best practices response to non-fail-stop failures can charitably be described as pragmatic: identify a root cause and add checksums to prevent that error from happening again in the future. Pragmatic responses have proven effective for patching holes and protecting against faults once they have occurred; unfortunately the initial damage has already been done, and it is difficult to say if the patches made to address previous faults will protect against future failures. We posit that an end-to-end solution based on Byzantine fault tolerant (BFT) state machine replication is an efficient and deployable alternative to current ad hoc approaches favored in general purpose computing. The replicated state machine approach ensures that multiple copies of the same deterministic application execute requests in the same order and provides end-to-end assurance that independent transient failures will not lead to unavailability or incorrect responses. An efficient and effective end-to-end solution covers faults that have already been observed as well as failures that have not yet occurred, and it provides structural confidence that developers won’t have to track down yet another failure caused by some unpredicted memory, disk, or network behavior. While the promise of end-to-end failure protection is intriguing, significant technical and practical challenges currently prevent adoption in general purpose computing environments. On the technical side, it is important that end-to-end solutions maintain the performance characteristics of deployed systems: if end-to- end solutions dramatically increase computing requirements, dramatically reduce throughput, or dramatically increase latency during normal operation then end- to-end techniques are a non-starter. On the practical side, it is important that end-to-end approaches be both comprehensible and easy to incorporate: if the cost of end-to-end solutions is rewriting an application or trusting intricate and arcane protocols, then end-to-end solutions will not be adopted. In this thesis we show that BFT state machine replication can and be used in deployed systems. Reaching this goal requires us to address both the technical and practical challenges previously mentioned. We revisiting disparate research results from the last decade and tweak, refine, and revise the core ideas to fit together into a coherent whole. Addressing the practical concerns requires us to simplify the process of incorporating BFT techniques into legacy applications.

DOWNLOAD TR-2023.pdf

TR-10-40

Nicholas K. Jong(1). "Structured Exploration for Reinforcement Learning". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-10-40 (dissertation). December 17th, 2010. 280 pages.

Reinforcement Learning (RL) offers a promising approach towards achieving the dream of autonomous agents that can behave intelligently in the real world. Instead of requiring humans to determine the correct behaviors or sufficient knowledge in advance, RL algorithms allow an agent to acquire the necessary knowledge through direct experience with its environment. Early algorithms guaranteed convergence to optimal behaviors in limited domains, giving hope that simple, universal mechanisms would allow learning agents to succeed at solving a wide variety of complex problems. In practice, the field of RL has struggled to apply these techniques successfully to the full breadth and depth of real-world domains. This thesis extends the reach of RL techniques by demonstrating the synergies among certain key developments in the literature. The first of these developments is model-based exploration, which facilitates theoretical convergence guarantees in finite problems by explicitly reasoning about an agent's certainty in its understanding of its environment. A second branch of research studies function approximation, which generalizes RL to infinite problems by artificially limiting the degrees of freedom in an agent's representation of its environment. The final major advance that this thesis incorporates is hierarchical decomposition, which seeks to improve the efficiency of learning by endowing an agent's knowledge and behavior with the gross structure of its environment. Each of these ideas has intuitive appeal and sustains substantial independent research efforts, but this thesis defines the first RL agent that combines all their benefits in the general case. In showing how to combine these techniques effectively, this thesis investigates the twin issues of generalization and exploration, which lie at the heart of efficient learning. This thesis thus lays the groundwork for the next generation of RL algorithms, which will allow scientific agents to know when it suffices to estimate a plan from current data and when to accept the potential cost of running an experiment to gather new data.

DOWNLOAD TR-2008.pdf

TR-10-32

Yulin Li(1). "The Diagrammatic Specification and Automatic Generation of Geometry Subroutines". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-10-32 (dissertation). August 30th, 2010. 165 pages.

Programming has advanced a great deal since the appearance of the stored-program architecture. Through the successive generations of machine codes, assembly languages, high-level languages, and object-oriented languages, the drive has been toward program descriptions that express more meaning in a shorter space. This trend continues today with domain-specific languages. However, conventional languages rely on a textual formalism (commands, statements, lines of code) to capture the programmer's intent, which, regardless of its level of abstraction, imposes inevitable overheads. Before successful programming activities can take place, the syntax has to be mastered, names and keywords memorized, the library routines mastered, etc. Existing visual programming languages avoid some of these overheads, but do not release the programmer from the task of specifying the program logic, which consumes the main portion of programming time and also is the major source of difficult bugs. Our work aims to minimize the demands a formalism imposes on the programmer of geometric subroutines other than what is inherent in the problem itself. Our approach frees the programmer from syntactic constraints and generates logically correct programs automatically from program descriptions in the form of diagrams. To write a program, the programmer simply draws a few diagrams to depict the problem context and specifies all the necessary parameters through menu operations. Diagrams are succinct, easy to learn, and intuitive to use. They are much easier to modify than code, and they help the user visualize and analyze the problem, in addition to providing information to the computer. Furthermore, diagrams describe a situation rather than a task and thus are reusable for different tasks—in general, a single diagram can generate many programs. For these reasons, we have chosen diagrams as the main specification mechanism. In addition, we leverage the power of automatic inference to reason about diagrams and generic components—the building blocks of our programs—and discover the logic for assembling these components into correct programs. To facilitate inference, symbolic facts encode entities present in the diagrams, their spatial relationships, and the preconditions and effects of reusable components. We have developed a reference implementation and tested it on a number of real-world examples to demonstrate the feasibility and efficacy of our approach.

DOWNLOAD TR-1991.pdf

TR-10-31

Indrajit Roy(1). "Protecting Sensitive Information from Untrusted Code". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-10-31 (dissertation). August 27th, 2010. 137 pages.

As computer systems support more aspects of modern life, from finance to health care, security is becoming increasingly important. However, building secure systems remains a challenge. Software continues to have security vulnerabilities due to reasons ranging from programmer errors to inadequate programming tools. Because of these vulnerabilities we need mechanisms that protect sensitive data even when the software is untrusted. This dissertation shows that secure and practical frameworks can be built for protecting users' data from untrusted applications in both desktop and cloud computing environment. Laminar is a new framework that secures desktop applications by enforcing policies written as information flow rules. Information flow control, a form of mandatory access control, enables programmers to write powerful, end-to-end security guarantees while reducing the amount of trusted code. Current programming abstractions and implementations of this model either compromise end-to-end security guarantees or require substantial modifications to applications, thus deterring adoption. Laminar addresses these shortcomings by exporting a single set of abstractions to control information flows through operating system resources and heap-allocated objects. Programmers express security policies by labeling data and represent access restrictions on code using a new abstraction called a security region. The Laminar programming model eases incremental deployment, limits dynamic security checks, and supports multithreaded programs that can access heterogeneously labeled data. In large scale, distributed computations safeguarding information requires solutions beyond mandatory access control. An important challenge is to ensure that the computation, including its output, does not leak sensitive information about the inputs. For untrusted code, access control cannot guarantee that the output does not leak information. This dissertation proposes Airavat, a MapReduce-based system which augments mandatory access control with differential privacy to guarantee security and privacy for distributed computations. Data providers control the security policy for their sensitive data, including a mathematical bound on potential privacy violations. Users without security expertise can perform computations on the data; Airavat prevents information leakage beyond the data provider's policy. Our prototype implementation of Airavat demonstrates that several data mining tasks can be performed in a privacy preserving fashion with modest performance overheads.

DOWNLOAD TR-1990.pdf

TR-10-30

Gregory Kuhlmann(1). "Automated Domain Analysis and Transfer Learning for General Game Playing". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-10-30 (dissertation). August 17th, 2010. 150 pages.

Creating programs that can play games such as chess, checkers, and backgammon, at a high level has long been a challenge and benchmark for AI. Computer game playing is arguably one of AI's biggest success stories. Several game playing systems developed in the past, such as Deep Blue, Chinook and TD-Gammon have demonstrated competitive play against the top human players. However, such systems are limited in that they play only one particular game and they typically must be supplied with game-specific knowledge. While their performance is impressive, it is difficult to determine if their success is due to generally applicable techniques or due to the human game analysis. A general game player is an agent capable of taking as input a description of a game's rules and proceeding to play without any subsequent human input. In doing so, the agent, rather than the human designer, is responsible for the domain analysis. Developing such a system requires the integration of several AI components, including theorem proving, feature discovery, heuristic search, and machine learning. In the general game playing scenario, the player agent is supplied with a game's rules in a formal language, prior to match play. This thesis contributes a collection of general methods for analyzing these game descriptions to improve performance. Prior work on automated domain analysis has focused on generating heuristic evaluation functions for use in search. The thesis builds upon this work by introducing a novel feature generation method. Also, I introduce a method for generating and comparing simple evaluation functions based on these features. I describe how more sophisticated evaluation functions can be generated through learning. Finally, this thesis demonstrates the utility of domain analysis in facilitating knowledge transfer between games for improved learning speed. The contributions are fully implemented with empirical results in the general game playing system.

DOWNLOAD TR-1989.pdf

TR-10-01

Kurt Dresner(1). "Autonomous Intersection Management". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-10-01 (dissertation). January 8th, 2010. 216 pages.

Artificial intelligence research is ushering in an era of sophisticated, mass-market transportation technology. While computers can fly a passenger jet better than a human pilot, people still face the dangerous yet tedious task of driving. Intelligent Transportation Systems (ITS) is the field focused on integrating information technology with vehicles and transportation infrastructure. Recent advances in ITS point to a future in which vehicles handle the vast majority of the driving task. Once autonomous vehicles become popular, interactions amongst multiple vehicles will be possible. Current methods of vehicle coordination will be outdated. The bottleneck for efficiency will no longer be drivers, but the mechanism by which those drivers' actions are coordinated. Current methods for controlling traffic cannot exploit the superior capabilities of autonomous vehicles. This thesis describes a novel approach to managing autonomous vehicles at intersections that decreases the amount of time vehicles spend waiting. Drivers and intersections in this mechanism are treated as autonomous agents in a multiagent system. In this system, agents use a new approach built around a detailed communication protocol, which is also a contribution of the thesis. In simulation, I demonstrate that this mechanism can significantly outperform current intersection control technology---traffic signals and stop signs. This thesis makes several contributions beyond the mechanism and protocol. First, it contains a distributed, peer-to-peer version of the protocol for low-traffic intersections. Without any requirement of specialized infrastructure at the intersection, such a system would be inexpensive and easy to deploy at intersections which do not currently require a traffic signal. Second, it presents an analysis of the mechanism's safety, including ways to mitigate some failure modes. Third, it describes a custom simulator, written for this work, which will be made publicly available following the publication of the thesis. Fourth, it explains how the mechanism is ``backward-compatible'' so that human drivers can use it alongside autonomous vehicles. Fifth, it explores the implications of using the mechanism at multiple proximal intersections. The mechanism, along with all available modes of operation, is implemented and tested in simulation, and I present experimental results that strongly attest to the efficacy of this approach.

DOWNLOAD TR-1948.pdf

TR-09-23

Nalini Belaramani(1). "Policy Architecture for Distributed Storage Systems". The University of Texas at Austin, Department of Computer Sciences(1). Report# TR-09-23 (dissertation). August 12th, 2009. 233 pages.

Distributed data storage is a building block for many distributed systems such as mobile file systems, web service replication systems, enterprise file systems, etc. New distributed data storage systems are frequently built as new environment, requirements or workloads emerge. The goal of this dissertation is to develop the science of distributed storage systems by making it easier to build new systems. In order to achieve this goal, it proposes a new policy architecture, PADS, that is based on two key ideas: first, by providing a set of common mechanisms in an underlying layer, new systems can be implemented by defining policies that orchestrate these mechanisms; second, policy can be separated into routing and blocking policy, each addresses different parts of the system design. Routing policy specifies how data flow among nodes in order to meet performance, availability, and resource usage goals, whereas blocking policy specifies when it is safe to access data in order to meet consistency and durability goals. This dissertation presents a PADS prototype that defines a set of distributed storage mechanisms that are sufficiently flexible and general to support a large range of systems, a small policy API that is easy to use and captures the right abstractions for distributed storage, and a declarative language for specifying policy that enables quick, concise implementations of complex systems. We demonstrate that PADS is able to significantly reduce development effort by constructing a dozen significant distributed storage systems spanning a large portion of the design space over the prototype. We find that each system required only a couple of weeks of implementation effort and required a few dozen lines of policy code.

DOWNLOAD tr09-23.pdf

AI08-7

Patrick Beeson. "Creating and Utilizing Symbolic Representations of Spatial Knowledge using Mobile Robots". The University of Texas at Austin, Department of Computer Sciences. Report# AI08-7 (ai dissertation). October 24, 2008. 248 pages.

A map is a description of an environment allowing an agent---a human,or in our case a mobile robot---to plan and perform effective actions.From a single location, an agent's sensors can not observe the whole structure of a complex, large environment. For this reason, the agent must build a map from observations gathered over time and space. We distinguish between large-scale space, with spatial structure larger than the agent's sensory horizon, and small-scale space, with structure within the sensory horizon. We propose a factored approach to mobile robot map-building that handles qualitatively different types of uncertainty by combining the strengths of topological and metrical approaches. Our framework is based on a computational model of the human cognitive map; thus it allows robust navigation and communication within several different spatial ontologies. Our approach factors the mapping problem into natural sub-goals: building a metrical representation for local small-scale spaces; finding a topological map that represents the qualitative structure of large-scale space; and (when necessary) constructing a metrical representation for large-scale space using the skeleton provided by the topological map. The core contributions of this thesis are a formal description of the Hybrid Spatial Semantic Hierarchy (HSSH), a framework for both small-scale and large-scale representations of space, and an implementation of the HSSH that allows a robot to ground the large-scale concepts of place and path in a metrical model of the local surround. Given metrical models of the robot's local surround, we argue that places at decision points in the world can be grounded by the use of a primitive called a gateway. Gateways separate different regions in space and have a natural description at intersections and in doorways. We provide an algorithmic definition of gateways, a theory of how they contribute to the description of paths and places, and practical uses of gateways in spatial mapping and learning.

DOWNLOAD UT-AI-TR-08-7.pdf

AI08-5

Matthew E. Taylor. "Autonomous Inter-Task Transfer in Reinforcement Learning Domains". The University of Texas at Austin, Department of Computer Sciences. Report# AI08-5 (ai dissertation). July 10, 2008. 319 pages.

Reinforcement learning (RL) methods have become popular in recent years because of their ability to solve complex tasks with minimal feedback. While these methods have had experimental successes and have been shown to exhibit some desirable properties in theory, the basic learning algorithms have often been found slow in practice. Therefore, much of the current RL research focuses on speeding up learning by taking advantage of domain knowledge, or by better utilizing agents' experience. The ambitious goal of transfer learning, when applied to RL tasks, is to accelerate learning on some target task after training on a different, but related, source task. This dissertation demonstrates that transfer learning methods can successfully improve learning in RL tasks via experience from previously learned tasks. Transfer learning can increase RL's applicability to difficult tasks by allowing agents to generalize their experience across learning problems. This dissertation presents inter-task mappings, the first transfer mechanism in this area to successfully enable transfer between tasks with different state variables and actions. Inter-task mappings have subsequently been used by a number of transfer researchers. A set of six transfer learning algorithms are then introduced. While these transfer methods differ in terms of what base RL algorithms they are compatible with, what type of knowledge they transfer, and what their strengths are, all utilize the same inter-task mapping mechanism. These transfer methods can all successfully use mappings constructed by a human from domain knowledge, but there may be situations in which domain knowledge is unavailable, or insufficient, to describe how two given tasks are related. We therefore also study how inter-task mappings can be learned autonomously by leveraging existing machine learning algorithms. Our methods use classification and regression techniques to successfully discover similarities between data gathered in pairs of tasks, culminating in what is currently one of the most robust mapping-learning algorithms for RL transfer. Combining transfer methods with these similarity-learning algorithms allows us to empirically demonstrate the plausibility of autonomous transfer. We fully implement these methods in four domains (each with different salient characteristics), show that transfer can significantly improve an agent's ability to learn in each domain, and explore the limits of transfer's applicability.

DOWNLOAD UT-AI-TR-08-5.pdf

TR-08-35

Jiandan Zheng. "URA: A Universal Data Replication Architecture". The University of Texas at Austin, Department of Computer Sciences. Report# TR-08-35 (dissertation). August 22, 2008. 177 pages.

Data replication is a key building block for large-scale distributed systems to improve availability, performance, and scalability. Because there is a fundamental trade-off between performance and consistency as well as between availability and consistency, systems must make trade-offs among these factors based on the demands and technologies of their target environments and workloads. Unfortunately, existing replication protocols and mechanisms are intrinsically entangled with specific policy assumptions. Therefore, to accommodate new trade-offs for new policy requirements, developers have to either build a new replication system from scratch or modify existing mechanisms. This dissertation presents a universal data replication architecture (URA) that cleanly separates mechanism and policy and supports Partial Replication (PR), Any Consistency (AC), and Topology Independence (TI) simultaneously. Our architecture yields two significant advantages. First, by providing a single set of mechanisms that capture the common underlying abstractions for data replication, URA can serve as a common substrate for building and deploying new replication systems. It therefore can significantly reduce the effort required to construct or modify a replication system. Second, by providing a set of general and flexible mechanisms independent of any specific policy, URA enables better trade-offs than any current system can provide. In particular, URA can simultaneously provide the three PRACTI properties while any existing system can provide at most two of them. Our experimental results and case-study systems confirm that universal data replication architecture is a way to build better replication systems and a better way to build replication systems.

DOWNLOAD tr08-35.pdf

AI07-349

Alden, Matthew E. "MARLEDA: Effective Distribution Estimation Through Markov Random Fields". The University of Texas at Austin, Departments of Computer Sciences. Report# AI07-349 (dissertation). September 24, 2007. 138 pages.

Many problems within the biological sciences, such as DNA sequencing, protein structure prediction, and molecular docking, are being approached computationally. These problems require sophisticated solution methods that understand the complex natures of biological domains. Traditionally, such solution methods are problem specific, but recent advances in generic problem-solvers furnish hope for a new breed of computational tools. The challenge is to develop methods that can automatically learn or acquire an understanding of a complex problem domain. Estimation of Distribution Algorithms (EDAs) are generic search methods that use statistical models to learn the structure of a problem domain. EDAs have been successfully applied to many difficult search problems, such as circuit design, optimizing Ising spin glasses, and various scheduling tasks. However, current EDAs contain ad hoc limitations that reduce their capacity to solve hard problems. This dissertation presents a new EDA method, the Markovian Learning Estimation of Distribution Algorithm (MARLEDA), that employs a Markov random field model. The model is learned in a novel way that overcomes previous ad hoc limitations. MARLEDA is shown to perform well on standard benchmark search tasks. A multiobjective extension of MARLEDA is developed for use in predicting the secondary structure of RNA molecules. The extension is shown to produce high-quality predictions in comparison with several contemporary methods, laying the groundwork for a new computational tool for RNA researchers.

DOWNLOAD UT-AI-TR-07-349.pdf

AI07-347

De Paula, Judah B. "Modeling the self-organization of color selectivity in the visual cortex". The University of Texas at Austin, Department of Computer Sciences. Report# AI07-347 (dissertation). August 21, 2007. 146 pages.

How does the visual cortex represent and process color? Experimental evidence from macaque monkey suggests that cells selective for color are organized into small, spatially separated blobs in V1, and stripes in V2. This organization is strikingly different from that of orientation and ocular dominance maps, which consist of large, spatially contiguous patterns. In this dissertation, a self-organizing model of the early visual cortex is constructed using natural color image input. The modeled V1 develops realistic color-selective receptive fields, ocular dominance stripes, orientation maps, and color-selective regions, while the modeled V2 also creates realistic color-selective and orientation-selective neurons. V1 color-selective regions are generally located in the center of ocular dominance stripes as they are in biological maps; the model predicts that color-selective regions become more widespread in both cortical regions when the amount of color in the training images is increased. The model also predicts that in V1 there are three types of color-selective regions (red-selective, green-selective, and blue-selective), and that a unique cortical activation pattern exists for each of the HSV colors. In both V1 and V2, when regions of different color-selectivity are located nearby, bands of color form with gradually changing color preferences. The model also develops lateral connections between cells that are selective for similar orientations, matching previous experimental results, and predicts that cells selective for color primarily connect to other cells with similar chromatic preferences. Thus the model replicates the known data on the organization of color preferences in V1 and V2, provides a detailed explanation for how this structure develops and functions, and leads to concrete predictions to test in future experiments.

DOWNLOAD UT-AI-TR-07-347.pdf

AI07-346

Kate, Rohit J. "Learning for Semantic Parsing with Kernels under Various Forms of Supervision". The University of Texas at Austin, Department of Computer Sciences. Report# AI07-346 (dissertation). August 21, 2007. 174 pages.

Semantic parsing involves deep semantic analysis that maps natural language sentences to their formal executable meaning representations. This is a challenging problem and is critical for developing computing systems that understand natural language input. This thesis presents a new machine learning approach for semantic parsing based on string-kernel-based classification. It takes natural language sentences paired with their formal meaning representations as training data. For every production in the formal language grammar, a Support-Vector Machine (SVM) classifier is trained using string similarity as the kernel. Meaning representations for novel natural language sentences are obtained by finding the most probable semantic parse using these classifiers. This method does not use any hard-matching rules and unlike previous and other recent methods, does not use grammar rules for natural language, probabilistic or otherwise, which makes it more robust to noisy input. Besides being robust, this approach is also flexible and able to learn under a wide range of supervision, from extra to weaker forms of supervision. It can easily utilize extra supervision given in the form of syntactic parse trees for natural language sentences by using a syntactic tree kernel instead of a string kernel. Its learning algorithm can also take advantage of detailed supervision provided in the form of semantically augmented parse trees. A simple extension using transductive SVMs enables the system to do semi-supervised learning and improve its performance utilizing unannotated sentences which are usually easily available. Another extension involving EM-like retraining makes the system capable of learning under ambiguous supervision in which the correct meaning representation for each sentence is not explicitly given, but instead a set of possible meaning representations is given. This weaker and more general form of supervision is better representative of a natural training environment for a language-learning system requiring minimal human supervision. For a semantic parser to work well, conformity between natural language and meaning representation grammar is necessary. However meaning representation grammars are typically designed to best suit the application which will use the meaning representations with little consideration for how well they correspond to natural language semantics. We present approaches to automatically transform meaning representation grammars to make them more compatible with natural language semantics and hence more suitable for learning semantic parsers. Finally, we also show that ensembles of different semantic parser learning systems can obtain the best overall performance.

DOWNLOAD UT-AI-TR-07-346.pdf

AI07-345

Bunescu, Razvan Constantin. "Learning for Information Extraction: From Named Entity Recognition and Disambiguation To Relation Extraction". The University of Texas at Austin, Department of Computer Sciences. Report# AI07-345 (dissertation). August 17, 2007. 168 pages.

Information Extraction, the task of locating textual mentions of specific types of entities and their relationships, aims at representing the information contained in text documents in a structured format that is more amenable to applications in data mining, question answering, or the semantic web. The goal of our research is to design information extraction models that obtain improved performance by exploiting types of evidence that have not been explored in previous approaches. Since designing an extraction system through introspection by a domain expert is a laborious and time consuming process, the focus of this thesis will be on methods that automatically induce an extraction model by training on a dataset of manually labeled examples. Named Entity Recognition is an information extraction task that is concerned with finding textual mentions of entities that belong to a predefined set of categories. We approach this task as a phrase classification problem, in which candidate phrases from the same document are collectively classified. Global correlations between candidate entities are captured in a model built using the expressive framework of Relational Markov Networks. Additionally, we propose a novel tractable approach to phrase classification for named entity recognition based on a special Junction Tree representation. Classifying entity mentions into a predefined set of categories achieves only a partial disambiguation of the names. This is further refined in the task of Named Entity Disambiguation, where names need to be linked to their actual denotations. In our research, we use Wikipedia as a repository of named entities and propose a ranking approach to disambiguation that exploits learned correlations between words from the name context and categories from the Wikipedia taxonomy. Relation Extraction refers to finding relevant relationships between entities mentioned in text documents. Our approaches to this information extraction task differ in the type and the amount of supervision required. We first propose two relation extraction methods that are trained on documents in which sentences are manually annotated for the required relationships. In the first method, the extraction patterns correspond to sequences of words and word classes anchored at two entity names occurring in the same sentence. These are used as implicit features in a generalized subsequence kernel, with weights computed through training of Support Vector Machines. In the second approach, the implicit extraction features are focused on the shortest path between the two entities in the word-word dependency graph of the sentence. Finally, in a significant departure from previous learning approaches to relation extraction, we propose reducing the amount of required supervision to only a handful of pairs of entities known to exhibit or not exhibit the desired relationship. Each pair is associated with a bag of sentences extracted automatically from a very large corpus. We extend the subsequence kernel to handle this weaker form of supervision, and describe a method for weighting features in order to focus on those correlated with the target relation rather than with the individual entities. The resulting Multiple Instance Learning approach offers a competitive alternative to previous relation extraction methods, at a significantly reduced cost in human supervision.

DOWNLOAD UT-AI-TR-07-345.pdf

AI07-344

Provost, Jefferson. "Reinforcement Learning in High-Diameter, Continuous Environments". The University of Texas at Austin, Department of Computer Sciences. Report# AI07-344 (dissertation). August 17, 2007. 116 pages.

Many important real-world robotic tasks have high diameter, that is, their solution requires a large number of primitive actions by the robot. For example, they may require navigating to distant locations using primitive motor control commands. In addition, modern robots are endowed with rich, high-dimensional sensory systems, providing measurements of a continuous environment. Reinforcement learning (RL) has shown promise as a method for automatic learning of robot behavior, but current methods work best on low-diameter, low-dimensional tasks. Because of this problem, the success of RL on real-world tasks still depends on human analysis of the robot, environment, and task to provide a useful set of perceptual features and an appropriate decomposition of the task into subtasks. This thesis presents Self-Organizing Distinctive-state Abstraction (SODA) as a solution to this problem. Using SODA a robot with little prior knowledge of its sensorimotor system, environment, and task can automatically reduce the effective diameter of its tasks. First it uses a self-organizing feature map to learn higher level perceptual features while exploring using primitive, local actions. Then, using the learned features as input, it learns a set of high-level actions that carry the robot between perceptually distinctive states in the environment. Experiments in two robot navigation environments demonstrate that SODA learns useful features and high-level actions, that using these new actions dramatically speeds up learning for high-diameter navigation tasks, and that the method scales to large (building-sized) robot environments. These experiments demonstrate SODAs effectiveness as a generic learning agent for mobile robot navigation, pointing the way toward developmental robots that learn to understand themselves and their environments through experience in the world, reducing the need for human engineering for each new robotic application.

DOWNLOAD UT-AI-TR-07-344.pdf

AI07-343

Wong, Yuk Wah. "Learning for Semantic Parsing and Natural Language Generation Using Statistical Machine Translation Techniques". The University of Texas at Austin, Department of Computer Sciences. Report# AI07-343 (dissertation). August 10, 2007. 203 pages.

One of the main goals of natural language processing (NLP) is to build automated systems that can understand and generate human lanugages. This goal has so far remained elusive. Existing hand-crafted systems can provide in-depth analysis of domain sub-languages, but are often notoriously fragile and costly to build. Existing machine-learned systems are considerably more robust, but are limited to relatively shallow NLP tasks. In this thesis, we present novel statistical methods for robust natural language understanding and generation. We focus on two important sub-tasks, semantic parsing and tactical generation. The key idea is that both tasks can be treated as the translation between natural languages and formal meaning representation languages, and therefore, can be performed using state-of-the-art statistical machine translation techniques. Specifically, we use a technique called synchronous parsing, which has been extensively used in syntax-based machine translation, as the unifying framework for semantic parsing and tactical generation. The parsing and generation algorithms learn all of their linguistic knowledge from annotated corpora, and can handle natural-language sentences that are conceptually complex. A nice feature of our algorithms is that the semantic parsers and tactical generators share the same learned synchronous grammars. Moreover, charts are used as the unifying language-processing architecture for efficient parsing and generation. Therefore, the generators are said to be the inverse of the parsers, an elegant property that has been widely advocated. Furthermore, we show that our parsers and generators can handle formal meaning representation languages containing logical variables, including predicate logic. Our basic semantic parsing algorithm is called WASP. Most of the other parsing and generation algorithms presented in this thesis are extensions of WASP or its inverse. We demonstrate the effectiveness of our parsing and generation algorithms by performing experiments in two real-world, restricted domains. Experimental results show that our algorithms are more robust and accurate than the currently best systems that require similar supervision. Our work is also the first attempt to use the same automatically-learned grammar for both parsing and generation. Unlike previous systems that require manually-constructed grammars and lexicons, our systems require much less knowledge engineering and can be easily ported to other languages and domains.

DOWNLOAD UT-AI-TR-07-343.pdf

AI07-342

Ramamoorthy, Subramanian. "Task Encoding, Motion Planning and Intelligent Control using Qualitative Models". The University of Texas at Austin, Department of Computer Sciences. Report# AI07-342 (dissertation (ph.d., advisor: prof. ben kuipers)). July 10, 2007. 179 pages.

This dissertation addresses the problem of trajectory generation for dynamical robots operating in unstructured environments in the absence of detailed models of the dynamics of the environment or of the robot itself. We factor this problem into the subproblem of task variation, and the subproblem of imprecision in models of dynamics. The problem of task variation is handled by defining task level control strategies in terms of qualitative models that support structurally stable phase space trajectories. Such models define low-dimensional spaces within which it is possible to select trajectories that constitute plans for achieving a desired goal. The second problem, that of model imprecision, arises when embedding the resulting trajectories in the phase space of the more complex higher-dimensional system that actually performs the task of interest. Trajectories in the high-dimensional phase space that are compatible with the low-dimensional plan are restricted to lie on a manifold. In the absence of analytical models of the high-dimensional dynamics, this manifold may be approximated using observed data generated by a randomized exploration of the state space. Approximations driven by such an imperfect set of observations can lead to spurious trajectories, but this problem is solved by regularizing the approximation using the low-dimensional model. This methodology is developed through a sequence of design problems. First, basic notions regarding control with qualitative models are clarified through the design of a global controller for the inverted pendulum and cart-pole systems. This is followed by the more challenging problem of dynamic bipedal walking on irregular terrain, which is the primary motivating problem for this dissertation. Our solution to the dynamic walking problem advances the state of the art by simultaneously achieving several important properties. Our algorithm generates trajectories to walk on irregular terrain, with only a qualitative model of the dynamics of the robot, and with energy usage comparable with actuated walkers utilizing passive dynamic principles. Although the definition of tasks in terms of structurally stable orbits and manifolds is very natural when talking about physical systems, this representation yields benefits in more artificial domains as well. This is demonstrated through the example of spatiotemporal control of polygonal shapes, such as in a robot collective.

DOWNLOAD UT-AI-TR-07-342.pdf

TR-07-29

Hanson, Heather. "Coordinated Power, Energy, and Temperature Management". The University of Texas at Austin, Department of Computer Sciences. Report# TR-07-29 (dissertation). June 18, 2007.

NO ABSTRACT

DOWNLOAD NOT AVAILABLE

AI06-327

Ge, Ruifang. "Learning Semantic Parsers Using Statistical Syntactic Parsing Techniques". The University of Texas at Austin, Department of Computer Sciences. Report# AI06-327 (doctoral dissertation proposal). February 13, 2006. 41 pages.

Most recent work on semantic analysis of natural language has focused on "shallow'' semantics such as word-sense disambiguation and semantic role labeling. Our work addresses a more ambitious task we call semantic parsing where natural language sentences are mapped to complete formal meaning representations. We present our system Scissor based on a statistical parser that generates a semantically-augmented parse tree (SAPT), in which each internal node has both a syntactic and semantic label. A compositional-semantics procedure is then used to map the augmented parse tree into a final meaning representation. Training the system requires sentences annotated with augmented parse trees. We evaluate the system in two domains, a natural-language database interface and an interpreter for coaching instructions in robotic soccer. We present experimental results demonstrating that Scissor produces more accurate semantic representations than several previous approaches on long sentences. In the future, we intend to pursue several directions in developing more accurate semantic parsing algorithms and automating the annotation process. This work will involve exploring alternative tree representations for better generalization in parsing. We also plan to apply discriminative reranking methods to semantic parsing, which allows exploring arbitrary, potentially correlated features not usable by the baseline learner. We also propose to design a method for automating the SAPT-generation process to alleviate the extra annotation work currently required for training Scissor. Finally, we will investigate the impact of different statistical syntactic parsers on semantic parsing using the automated SAPT-generation process.

DOWNLOAD UT-AI-TR-06-327.pdf

TR-06-66

Martin, Jean-Philippe. "Byzantine Fault-Tolerance and Beyond". The University of Texas at Austin, Department of Computer Sciences. Report# TR-06-66 (ph.d. dissertation). December 6, 2006. 291 pages.

Byzantine fault-tolerance techniques are useful because they tolerate arbitrary faults regardless of cause: bugs, hardware glitches, even hackers. These techniques have recently gained popularity after it was shown that they could be made practical. Most of the dissertation builds on Byzantine fault-tolerance (BFT) and extends it with new results for Byzantine fault-tolerance for both quorum systems and state machine replication. Our contributions include proving new lower bounds, finding new protocols that meet these bounds, and providing new functionality at lower cost through a new architecture for state machine replication. The second part of the dissertation goes beyond Byzantine fault-tolerance. We show that BFT techniques are not sufficient for networks that span multiple administrative domains, propose the new BAR model to describe these environments, and show how to build BAR-Tolerant protocols through our example of a BAR-Tolerant terminating reliable broadcast protocol.

DOWNLOAD tr06-66.pdf

TR-06-46

Bientinesi, Paolo. "Mechanical Derivation and Systematic Analysis of Correct Linear Algebra Algorithms". The University of Texas at Austin, Department of Computer Sciences. Report# TR-06-46 (phd dissertation). September 29, 2006. 149 pages.

We consider the problem of developing formally correct dense linear algebra libraries. The problem would be solved convincingly if, starting from the mathematical specification of a target operation, it were possible to generate, implement and analyze a family of correct algorithms that compute the operation. This thesis presents evidence that for a class of dense linear operations, systematic and mechanical development of algorithms is within reach. It describes and demonstrates an approach for deriving and implementing, systematically and even mechanically, proven correct algorithms. It also introduces a systematic procedure to analyze, in a modular fashion, numerical properties of the generated algorithms.

DOWNLOAD tr06-46.pdf

TR-06-45

Lopez-Herrejon, Roberto Erick. "Understanding Feature Modularity". The University of Texas at Austin, Department of Computer Sciences. Report# TR-06-45 (phd dissertation). September 28, 2006. 145 pages.

Features are increments in program functionality. Feature abstraction, the process of abstracting programs into their constituent features, is a relatively common yet informal practice in software design. It is common because it simplifies program understanding. It is also important for software product lines whose essence is the systematic and efficient creation of software products from a shared set of assets or features, where each product exhibits common functionality with other products but also has unique functionalities. Thus, it seems natural to modularize feature abstractions and use such modules as building blocks of programs and product lines. Unfortunately, conventional modularization approaches such as methods, classes and packages are not geared for supporting feature modules. They present two recurrent problems. First, a typical feature implementation is spread over several conventional modules. Second, features are usually more than source code artifacts as they can modularize many different program representations (makefiles, documentation, performance models). An undesirable consequence is that developers must lower their abstractions from features to those provided by the underlying implementation languages, a process that is far from simple let alone amenable to significant automation. The conceptual gap created between feature abstractions and their modularization hinders program understanding and product line development. The root of the problem is the fact that feature modularity is not well understood and thus not well supported in conventional programming languages, modularization mechanisms, and design techniques. In this dissertation, we explore language and modularity support for features founded on an algebraic model geared for program synthesis. Our model integrates ideas from collaboration-based designs, mixin layers, aspect oriented programming, multi-dimensional separation of concerns, and generative programming. We assess our model with an implementation of a non-trivial product line case study, and evaluate feature support in emerging modularization technologies.

DOWNLOAD tr06-45.pdf

AI05-326

Kate, Rohit J. "A Kernel-based Approach to Learning Semantic Parsers". The University of Texas at Austin, Department of Computer Sciences. Report# AI05-326 (doctoral dissertation proposal). November 22, 2005. 34 pages.

Semantic parsing involves deep semantic analysis that m.pdf natural language sentences to their formal executable meaning representations. This is a challenging problem and is critical for developing user-friendly natural language interfaces to computing systems. Most of the research in natural language understanding, however, has mainly focused on shallow semantic analysis like case-role analysis or word sense disambiguation. The existing work in semantic parsing either lack the robustness of statistical methods or are applicable only to simple domains where semantic analysis is equivalent to filling a single semantic frame. In this proposal, we present a new approach to semantic parsing based on string-kernel-based classification. Our system takes natural language sentences paired with their formal meaning representations as training data. For every production in the formal language grammar, a Support-Vector Machine (SVM) classifier is trained using string similarity as the kernel. Each classifier then gives the probability of the production covering any given natural language string of words. These classifiers are further refined using EM-type iterations based on their performance on the training data. Meaning representations for novel natural language sentences are obtained by finding the most probable semantic parse using these classifiers. Our experiments on two real-world data sets that have deep meaning representations show that this approach compares favorably to other existing systems in terms of accuracy and coverage. For future work, we propose to extend this approach so that it will also exploit the knowledge of natural language syntax by using the existing syntactic parsers. We also intend to broaden the scope of application domains, for example, domains where the sentences are noisy as typical in speech, or domains where corpora available for training do not have natural language sentences aligned with their unique meaning representations. We aim to test our system on the task of complex relation extraction as well. Finally, we also plan to investigate ways to combine our semantic parser with some recently developed semantic parsers to form committees in order to get the best overall performance.

DOWNLOAD UT-AI-TR-05-326.pdf

TR-05-49

Melville, Prem. "Creating Diverse Ensemble Classifiers to Reduce Supervision". The University of Texas at Austin, Department of Computer Sciences. Report# TR-05-49 (dissertation). December 13, 2005. 157 pages.

Ensemble methods like Bagging and Boosting which combine the decisions of multiple hypotheses are some of the strongest existing machine learning methods. The diversity of the members of an ensemble is known to be an important factor in determining its generalization error. In this thesis, we present a new method for generating ensembles, DECORATE (Diverse Ensemble Creation by Oppositional Relabeling of Artificial Training Examples), that directly constructs diverse hypotheses using additional artificially-generated training examples. The technique is a simple, general meta-learner that can use any strong learner as a base classifier to build diverse committees. The diverse ensembles produced by DECORATE are very effective for reducing the amount of supervision required for building accurate models. The first task we demonstrate this on is classification given a fixed training set. Experimental results using decision-tree induction as a base learner demonstrate that our approach consistently achieves higher predictive accuracy than the base classifier, Bagging and Random Forests. Also, DECORATE attains higher accuracy than Boosting on small training sets, and achieves comparable performance on larger training sets. Additional experiments demonstrate DECORATE's resilience to imperfections in data, in the form of missing features, classification noise, and feature noise. DECORATE ensembles can also be used to reduce supervision through active learning, in which the learner selects the most informative examples from a pool of unlabeled examples, such that acquiring their labels will increase the accuracy of the classifier. Query by Committee is one effective approach to active learning in which disagreement within the ensemble of hypotheses is used to select examples for labeling. Query by Bagging and Query by Boosting are two practical implementations of this approach that use Bagging and Boosting respectively, to build the committees. For efficient active learning it is critical that the committee be made up of consistent hypotheses that are very different from each other. Since DECORATE explicitly builds such committees, it is well-suited for this task. We introduce a new algorithm, Active-DECORATE, which uses DECORATE committees to select good training examples. Experimental results demonstrate that Active-DECORATE typically requires labeling fewer examples to achieve the same accuracy as Query by Bagging and Query by Boosting. Apart from optimizing classification accuracy, in many applications, producing good class probability estimates is also important, e.g., in fraud detection, which has unequal misclassification costs. This thesis introduces a novel approach to active learning based on Active-DECORATE which uses Jensen-Shannon divergence (a similarity measure for probability distributions) to improve the selection of training examples for optimizing probability estimation. Comprehensive experimental results demonstrate the benefits of our approach. Unlike the active learning setting, in many learning problems the class labels for all instances are known, but feature values may be missing and can be acquired at a cost. For building accurate predictive models, acquiring complete information for all instances is often quite expensive, while acquiring information for a random subset of instances may not be optimal. We formalize the task of active feature-value acquisition, which tries to reduce the cost of achieving a desired model accuracy by identifying instances for which obtaining complete information is most informative. We present an approach, based on DECORATE, in which instances are selected for acquisition based on the current model's accuracy and its confidence in the prediction. Experimental results demonstrate that our approach can induce accurate models using substantially fewer feature-value acquisitions than random sampling.

DOWNLOAD tr05-49.pdf

TR-05-36

Kim, Min Sik. "Buildling and Maintaining Overlay Networks for Bandwidth-Demanding Applications". The University of Texas at Austin, Department of Computer Sciences. Report# TR-05-36 (dissertation). July 11, 2005. 171 pages.

The demands of Internet applications have grown significantly in terms of required resources and types of services. Overlay networks have emerged to accommodate such applications by implementing more services on top of IP (Internet Protocol). However, while overlay networks are successful in circumventing limitations of IP, the task of building and maintaining an overlay network is still challenging. In an overlay network, participating hosts are virtually fully-connected through the underlying Internet. However, since the quality of overlay connections varies, the performance of the overlay network is dependent on which connections are chosen to be utilized. Therefore, maintaining a ``good'' overlay network topology is crucial in achieving high performance. To demonstrate how much performance gain can be achieved through topology changes, a distributed algorithm to build an overlay multicast tree is proposed for streaming media distribution. The algorithm finds an optimal tree such that the average bandwidth of receivers is maximized under an abstract network model. However, increasing bandwidth does not necessarily lead to a better overlay topology; in overlay networks, interference between overlay connections should be taken into account. Since such interference occurs when different overlay connections pass through a congested link simultaneously, detecting congestion shared by multiple overlay connections is necessary to avoid bottlenecks. For shared congestion detection, a novel technique called DCW (Delay Correlation with Wavelet denoising) is proposed. Previous techniques to detect shared congestion have limitations in applying to overlay networks; they assume a common source or destination node, drop-tail queueing, or a single point of congestion. However, DCW is applicable to any pair of paths on the Internet without such limitations. It employs a signal processing method, wavelet denoising, to separate queueing delay caused by network congestion from various other delay variations. The proposed technique is evaluated through both simulations and Internet experiments. They show that for paths with a common synchronization point, DCW provides faster convergence and higher accuracy while using fewer packets than previous techniques. Furthermore, DCW is robust and accurate without a synchronization point; more specifically, it can tolerate a synchronization offset of up to one second between two packet flows. Because DCW is designed to detect shared congestion between a pair of paths, there is a concern about scalability when it is used in a large-scale overlay network. To cluster N paths, a straightforward approach of using pairwise tests would require O(N^2) time complexity. To address this issue, a scalable approach to cluster Internet paths using multidimensional indexing is presented. By storing per-path data in a multidimensional space indexed using a tree-like structure, the computational complexity of clustering is reducible to O(N log N). The indexing overhead can be further improved by reducing dimensionality of the space through the wavelet transform. Computation cost is kept low by using the same wavelet transform for both denoising in DCW and dimensionality reduction. The proposed approach is evaluated using simulations and found to be effective for large N. The tradeoff between indexing overhead and clustering accuracy is shown empirically. As a case study, an algorithm that improves overlay multicast topology is designed. Because overlay multicast forwards data without support from routers, data may be delivered multiple times over the same physical link, causing a bottleneck. This problem is more serious for applications demanding high bandwidth such as multimedia distribution. Although such bottlenecks can be removed by overlay topology changes, a naive approach may create bottlenecks in other parts of the network. The proposed algorithm removes all bottlenecks caused by the redundant data delivery of overlay multicast, detecting such bottlenecks using DCW. In a case where the source rate is constant and the available bandwidth of each link is not less than the rate, the algorithm guarantees that every node receives at the full source rate. Simulation results show that even in a network with a dense receiver population, the algorithm finds a tree that satisfies all the receiving nodes while other heuristic-based approaches often fail. A similar approach to finding bottlenecks and removing them through topology changes is applicable to other types of overlay networks. This research will enable bandwidth-demanding applications to build more efficient overlay networks to achieve higher throughput.

DOWNLOAD tr05-36.pdf

TR-05-33

Zhang, Xincheng. "Protocol Design for Scalable and Reliable Group Rekeying Divergences". The University of Texas at Austin, Department of Computer Sciences. Report# TR-05-33 (technical report-dissertation). June 29, 2005. 183 pages.

In secure group communications, group users share a symmetric key, called group key. The group key is used for encrypting data traffic among group users or restricting access to resources intended for group users only. A key server needs to change the group key after users join and leave (called group rekeying), by composing a rekey message that consists of encrypted new keys (encryptions, in short) and delivering it to all users. When group size is large, it becomes infeasible to rekey per user join or leave because of its high processing and bandwidth overheads. Instead, the key server changes the group key per rekey interval, the length of which indicates how tight the group access control is. It is desired to reduce the overhead of group rekeying as much as possible in order to allow frequent rekeying. To address the scalability issue of the key server, Wong, Gouda, and Lam proposed the key tree approach in 1998. The same idea also appears in RFC 2627. The scalability of rekey transport, however, was not addressed. The objective of this dissertation is to design a scalable and reliable rekey transport protocol and evaluate its performance. Rekey transport differs from data transport because rekey messages require scalable, reliable, and real-time delivery. Furthermore, each user needs only a small subset of all of the encryptions in a rekey message. We have proposed a scalable and reliable rekey transport protocol; its efficiency benefits from the special properties of rekey transport. The protocol runs in two st.pdf: a multicast step followed by a unicast recovery step. Proactive forward error correction (FEC) is used in multicast to reduce delivery latency and limit the number of users who need unicast recovery. The unicast recovery step provides eventual reliability; it also reduces the worst-case delivery latency as well as user bandwidth overhead. In the protocol design, various technical issues are addressed. First, a key identification scheme is proposed for each user to identify the subset of new keys that it needs. The communication cost of this scheme is only several bytes per packet. Second, we investigate how to space the sending times of packets to make proactive FEC resilient to burst loss. Lastly, an adaptive FEC scheme is proposed to make the number of users who need unicast recovery controlled around a small target value under dynamic network conditions. This scheme also makes FEC bandwidth overhead and rekey interval close to the the feasible minima. Application-layer multicast (ALM) offers new opportunities to do naming and routing. In the dissertation, we have studied how to use ALM to support concurrent rekey and data transport in secure group communications. Rekey traffic is bursty and requires fast delivery. It is desired to reduce rekey bandwidth overhead as much as possible since it competes for available bandwidth with data traffic. Towards this goal, we propose a multicast scheme that exploits proximity in the underlying network. We further propose a rekey message splitting scheme to significantly reduce rekey bandwidth overhead at each user access link and network link. We formulate and prove correctness properties for the multicast scheme and rekey message splitting scheme. Simulation results show that our approach can reduce rekey bandwidth overhead from several thousand encryptions to less than ten encryptions for more than 90% of users in a group of 1024 users.

DOWNLOAD tr05-33.pdf

TR-05-32

Liu, Huaiyu. "Designing a Resilient Routing Infrastructure for Peer-to-Peer Networks Protocols". The University of Texas at Austin, Department of Computer Sciences. Report# TR-05-32 (ph.d. dissertation). June 28, 2005. 231 pages.

Peer-to-Peer (P2P) networks have enabled a new generation of large scale distributed applications. Unlike the traditional client-server model, in a P2P network, all peers in the network both contribute to and receive services from the network. Due to their decentralized and self-organizing nature, P2P networks enable tens of thousands (potentially millions) of Internet machines to form virtual communities and share the vast resources aggregated from the participating machines. In this dissertation, we address a fundamental problem in designing P2P networks: How to construct and maintain a resilient infrastructure to provide reliable, scalable, and efficient routing service for millions of Internet nodes without central service and administration? The absence of central administration, the large number of nodes involved, and the high rate of node dynamics pose great challenges to the design of a resilient routing infrastructure for P2P networks. Our work tackles the above challenges and has successfully addressed the following problems: (1) How to design protocols to maintain ``consistency" of routing tables to ensure successful routing? (2) How to reason about correctness of these protocols? (3) How to evaluate the system's ability to sustain high rates of node dynamics and how to improve this ability? In particular, we have designed a suite of protocols that construct and maintain a resilient routing infrastructure. To base the protocol design on a sound foundation, we have introduced a theoretical foundation, called C-set trees, to guide protocol design and correctness reasoning. Based on the theoretical foundation, we have designed a join protocol and developed rigorous correctness proofs for the protocol. We have also designed an efficient failure recovery protocol, which has been demonstrated by extensive simulations to perform perfect recovery even when 50% of network nodes fail. Both the join protocol and the failure recovery protocol have been integrated into a single framework following a module composition approach. Furthermore, we have conducted extensive simulation experiments to study behaviors of the designed system under different rates of node dynamics (churn experiments). We find our system to be effective, efficient, and provide reliable and scalable routing service for an average node lifetime as low as 8.3 minutes (the median lifetime measured for two deployed P2P networks, N.pdfter and Gnutella, was 60 minutes). Based on our system design, we have implemented a prototype system, named Silk, as the routing component of a shared infrastructure for P2P networks and other large-scale distributed applications.

DOWNLOAD tr05-32.pdf

AI04-314

Stanley, Kenneth Owen. "Efficient Evolution of Neural Networks through Complexification". The University of Texas at Austin, Department of Computer Sciences. Report# AI04-314 (dissertation). August 2004. 180 pages.

Artificial neural networks can potentially control autonomous robots, vehicles, factories, or game players more robustly than traditional approaches. Neuroevolution, i.e. the artificial evolution of neural networks, is a method for finding the right topology and connection weights to specify the desired control behavior. The challenge for neuroevolution is that difficult tasks may require complex networks with many connections, all of which must be set to the right values. Even if a network exists that can solve the task, evolution may not be able to find it in such a high-dimensional search space. This dissertation presents the NeuroEvolution of Augmenting Topologies (NEAT) method, which makes search for complex solutions feasible. In a process called complexification, NEAT begins by searching in a space of simple networks, and gradually makes them more complex as the search progresses. By starting minimally, NEAT is more likely to find efficient and robust solutions than neuroevolution methods that begin with large fixed or randomized topologies; by elaborating on existing solutions, it can gradually construct even highly complex solutions. In this dissertation, NEAT is first shown faster than traditional approaches on a challenging reinforcement learning benchmark task. Second, by building on existing structure, it is shown to maintain an "arms race" even in open-ended coevolution. Third, NEAT is used to successfully discover complex behavior in three challenging domains: the game of Go, an automobile warning system, and a real-time interactive video game. Experimental results in these domains demonstrate that NEAT makes entirely new applications of machine learning possible.

DOWNLOAD UT-AI-TR-04-314.pdf

AI04-311

Nahm, Un Yong. "Text Mining with Information Extraction". The University of Texas at Austin, Department of Computer Sciences. Report# AI04-311 (dissertation). October 2004. 132 pages.

The popularity of the Web and the large number of documents available in electronic form has motivated the search for hidden knowledge in text collections. Consequently, there is growing research interest in the general topic of text mining. In this paper, we develop a text-mining system by integrating methods from Information Extraction (IE) and Data Mining (Knowledge Discovery from Databases or KDD). By utilizing existing IE and KDD techniques, text-mining systems can be developed relatively rapidly and evaluated on existing text corpora for testing IE systems. We present a general text-mining framework called DiscoTEX which employs an IE module for transforming natural-language documents into structured data and a KDD module for discovering prediction rules from the extracted data. When discovering patterns in extracted text, strict matching of strings is inadequate because textual database entries generally exhibit variations due to typographical errors, misspellings, abbreviations, and other sources. We introduce the notion of discovering "soft-matching" rules from text and present two new learning algorithms. TextRISE is an inductive method for learning soft-matching prediction rules that integrates rule-based and instance-based learning methods. Simple, interpretable rules are discovered using rule induction, while a nearest-neighbor algorithm provides soft matching. SoftApriori is a text-mining algorithm for discovering association rules from texts that uses a similarity measure to allow flexible matching to variable database items. We present experimental results on inducing prediction and association rules from natural-language texts demonstrating that TextRISE and SoftApriori learn more accurate rules than previous methods for these tasks. We also present an approach to using rules mined from extracted data to improve the accuracy of information extraction. Experimental results demonstate that such discovered patterns can be used to effectively improve the underlying IE method.

DOWNLOAD UT-AI-TR-04-311.pdf

AI04-310

Mayberry III, Marshall R. "Incremental Nonmonotonic Parsing through Semantic Self-Organization". The University of Texas at Austin, Department of Computer Sciences. Report# AI04-310 (dissertation). May 2003. 148 pages.

Subsymbolic systems have been successfully used to model several aspects of human language processing. Subsymbolic parsers are appealing because they allow combining syntactic, semantic, and thematic constraints in sentence interpretation and nonmonotonically revising that interpretation while incrementally processing a sentence. Such parsers are also cognitively plausible: processing is robust and multiple interpretations are simultaneously activated when the input is ambiguous. Yet, it has proven very difficult to scale them up to realistic language. They have limited memory capacity, training takes a long time, and it is difficult to represent linguistic structure. A new connectionist model, INSOMNet, scales up the subsymbolic approach by utilizing semantic self-organization. INSOMNet was trained on semantic dependency graph representations from the recently-released LinGO Redwoods HPSG Treebank of sentences from the VerbMobil project. The results show that INSOMNet accurately learns to represent these semantic dependencies and generalizes to novel structures. Further evaluation of INSOMNet on the original VerbMobil sentences transcribed with annotations for spoken language demonstrates robust parsing of noisy input, while graceful degradation in performance from adding noise to the network weights underscores INSOMNet's tolerance to damage. Finally, the cognitive plausibility of the model is shown on a standard psycholinguistic benchmark, in which INSOMNet demonstrates expectations and defaults, coactivation of multiple interpretations, nonmonotonicity, and semantic priming.

DOWNLOAD UT-AI-TR-04-310.pdf

TR-04-36

Li, Xiaozhou. "Ranch: A Dynamic Network Topology". The University of Texas at Austin, Department of Computer Sciences. Report# TR-04-36 (dissertation). August 2004. 166 pages.

Peer-to-peer computing is an emerging paradigm that has the potential of harnessing enormous amounts of under-utilized computational resources (e.g., home computers). A central problem in peer-to-peer computing is how to organize the network nodes so that sophisticated applications can be efficiently supported. The cornerstone of a peer-to-peer network is a dynamic network topology that determines the neighbor relationships to be maintained by the network nodes. This dissertation is concerned with algorithmic and concurrency issues in dynamic network topologies. We present Ranch (random cyclic hypercube), a simple, recursive topology consisting of a collection of rings. Ranch is a scalable topology. In particular, it has logarithmic in-degree, out-degree, and diameter, and it uses only a logarithmic number of messages for a node to join or leave the network. Ranch also has a number of additional desirable properties, including locality awareness and fault tolerance. We show how to build a name resolution scheme for Ranch that enables the peer-to-peer network to find data items efficiently. Our results include a name replication scheme and a fault-tolerant lookup algorithm. We address the problem of topology maintenance in peer-to-peer networks, that is, how to properly update the neighbor variables when nodes join and leave the network, possibly concurrently. We design, and prove the correctness of, protocols that maintain the ring topology, the basis of several peer-to-peer networks, in the fault-free environment. Our protocols handle both joins and leaves actively (i.e., they update the neighbor variables as soon as a join or a leave occurs). We use an assertional method to prove the correctness of our protocols, that is, we first design a global invariant for a protocol and then show that every action of the protocol preserves the invariant. Our protocols are simple and our proofs are rigorous and explicit. We extend our results on the maintenance of rings to address the maintenance of Ranch. We present active and concurrent maintenance protocols that handle both joins and leaves for Ranch, along with their assertional correctness proofs. The protocols for Ranch use the protocols for rings as a building block. The protocols and the correctness proofs for Ranch substantially extend those for rings. We present simulation results that demonstrate the scalability and locality awareness of Ranch.

DOWNLOAD tr04-36.pdf

TR-04-34

Chaput, Harold Henry. "The Constructivist Learning Architecture: A Model of Cognitive Development for Robust Autonomous Robots". The University of Texas at Austin, Department of Computer Sciences. Report# TR-04-34 (dissertation). August 2004. 91 pages.

Autonomous robots are used more and more in remote and inaccessible places where they cannot be easily repaired if damaged or improperly programmed. A system is needed that allows these robots to repair themselves by recovering gracefully from damage and adapting to unforeseen changes. Newborn infants employ such a system to adapt to a new and dynamic world by building a hierarchical representation of their environment. This model allows them to respond robustly to changes by falling back to an earlier stage of knowledge, rather than failing completely. A computational model that replicates these phenomena in infants would afford a mobile robot the same adaptability and robustness that infants have. This dissertation presents such a model, the Constructivist Learning Architecture (CLA), that builds a hierarchical knowledge base using a set of interconnected self-organizing learning modules. The dissertation then demonstrates that CLA (1) replicates current studies in infant cognitive development, (2) builds sensorimotor schemas for robot control, (3) learns a goal-directed task from delayed rewards, and (4) can fall back and recover gracefully from damage. CLA is a new approach to robot control that allows robots to recover from damage or adapt to unforeseen changes in the environment. CLA is also a new approach to cognitive modeling that can be used to better understand how people learn for their environment in infancy and adulthood.

DOWNLOAD tr04-34.pdf

TR-04-29

Xie, Fei. "Integration of Model Checking into Software Development Processes". The University of Texas at Austin, Department of Computer Sciences. Report# TR-04-29 (dissertation). August 2004. 163 pages.

Testing has been the dominant method for validation of software systems. As software systems become complex, conventional testing methods have become inadequate. Model checking is a powerful formal verification method. It supports systematic exploration of all states or execution paths of the system being verified. There are two major challenges in practical and scalable application of model checking to software systems: (1) the applicability of model checking to software systems and (2) the intrinsic complexity of model checking. In this dissertation, we have developed a comprehensive approach to integration of model checking into two emerging software development processes: Model-Driven Development (MDD) and Component-Based Development (CBD), and a combination of MDD and CBD. This approach addresses the two major challenges under the following framework: (1) bridging applicability gaps through automatic translation of software representations to directly model-checkable formal representations, (2) seamless integration of state space reduction algorithms in the translation through static analysis, and (3) scaling model checking capability and achieving state space reduction by systematically exploring compositional structures of software systems. We have integrated model checking into MDD by applying mature model checking techniques to industrial design-level software representations through automatic translation of these representations to the input formal representations of model checkers. We have developed a translation-based approach to compositional reasoning of software systems, which simplifies the proof, implementation, and application of compositional reasoning rules at the software system level by reusing the proof and implementation of existing compositional reasoning rules for directly model-checkable formal representations. We have developed an integrated state space reduction framework which systematically conducts a top-down decomposition of a large and complex software system into directly model-checkable components by exploring domain-specific knowledge. We have designed, implemented, and applied a bottom-up approach to model checking of component-based software systems, which composes verified systems from verified components and integrates model checking into CBD. We have further scaled model checking of component-based systems by exploring the synergy between MDD and CBD, i.e., specifying components in executable design languages, and realizing the bottom-up approach based on model checking of software designs through translation.

DOWNLOAD tr04-29.pdf

TR-04-12

McGuire, Tommy. "Correct Implementation of Network Protocols". The University of Texas at Austin, Department of Computer Sciences. Report# TR-04-12 (dissertation). April 2004.. 190 pages.

A number of issues combine to make network protocol development significantly more difficult than other areas of computer programming: problems with time, concurrency, and failures; interactions between the network protocol and its environment; and obstacles in developing the protocol over time. In order to address these issues, we introduce the Timed Abstract Protocol notation and the Austin Protocol Compiler. The Timed Abstract Protocol, or TAP, notation is a domain-specific formal language for describing asynchronous message-passing network protocols, with two execution models: an abstract execution model and a concrete execution model. The abstract execution model is suited for protocol design, comprehension, and correctness verification. The concrete execution model is suited for protocol implementation. We show that the two models are equivalent: that a protocol interpreted under the concrete model preserves the intended behavior of the protocol interpreted under the abstract model. The Austin Protocol Compiler, or APC, is a system that transforms a protocol given in the Timed Abstract Protocol notation into executable C code and provides a runtime environment for the protocol. In order to demonstrate the effectiveness of the TAP notation and APC, we present implementations of a secure encryption key exchange protocol, a failure discovery protocol, and a Domain Name System server. While discussing the latter, we examine the performance of the APC implementation and show that it is comparable to two other DNS servers. The combination of the Timed Abstract Protocol notation and the Austin Protocol Compiler addresses the issues of network protocol development by allowing precise and verifiable descriptions of protocols which can be made executable easily, in order both to gain experimental experience and to provide reference implementations.

DOWNLOAD tr04-12.pdf

AI03-303

Gomez, Faustino J. "Robust Non-Linear Control through Neuroevolution". The University of Texas at Austin, Department of Computer Sciences. Report# AI03-303 (dissertation). August 2003. 150 KEY WORDS: Neural Networks, Genetic Algorithms, Non-Linear Control, Shaping pages.

Many complex control problems require sophisticated solutions that are not amenable to traditional controller design. Not only is it difficult to model real world systems, but often it is unclear what kind of behavior is required to solve the task. Reinforcement learning approaches have made progress in such problems, but have so far not scaled well. Neuroevolution, has improved upon conventional reinforcement learning, but has still not been successful in full-scale, non-linear control problems. This dissertation develops a methodology for solving real world control tasks consisting of three components: (1) an efficient neuroevolution algorithm that solves difficult non-linear control tasks by coevolving neurons, (2) an incremental evolution method to scale the algorithm to the most challenging tasks, and (3) a technique for making controllers robust so that they can transfer from simulation to the real world. The method is faster than other approaches on a set of difficult learning benchmarks, and is used in two full-scale control tasks demonstrating its applicability to real world problems.

DOWNLOAD UT-AI-TR-03-303.pdf

TR-03-56

Page, David Scott. "Effective Data Access in Software IO Frameworks". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-56 (dissertation). Fall 2003. 145 pages.

NO ABSTRACT

DOWNLOAD tr03-56.pdf

TR-03-45

Howell, Jo Ann Shaw. "On the Reduction of a Matrix to Frobenius Form Using Residue Arithmetic". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-45 (dissertation). August 1971. 129 pages.

This thesis is concerned with the reduction of an integral matrix to Frobenius form exactly using residue arithmetic. Thus, exact integral factors of the characteristic polynomial are obtained. The algorithm is based on a modification of the Danilewski method. This algorithm can be performed using either single-modulus or multiple-modulus residue arithmetic, and examples are given for both cases. Included in this thesis is a description of the Danilewski method. The theory of residue arithmetic for integers, matrices, and polynomials is surveyed in order to provide an adequate background for describing the modified Danilewski method. The selection of the moduli is discussed, and numerical results from a computer program are given.

DOWNLOAD tr03-45a.pdf tr03-45b.pdf tr03-45c.pdf

TR-03-35

Pettie, Seth. "On the Shortest Path and Minimum Spanning Tree Problems". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-35 (dissertation). August 2003. 204 pages.

The shortest path and minimum spanning tree problems are two of the classic textbook problems in combinatorial optimization. They are simple to describe and admit simple polynomial-time algorithms. However, despite years of concerted research effort, the asymptotic complexity of these problems remains unresolved. The main contributions of this dissertation are a number of asymptotically faster algorithms for the minimum spanning tree and shortest path problems. Of equal interest, we provide some clues as to why these problems are so difficult. In particular, we show why certain modern approaches to the problems are doomed to have super-linear complexity. A sampling of our results are listed below. We emphasize that all of our algorithms work with general graphs, and make no restrictive assumptions on the numerical representation of edge-lengths. (1) A provably optimal deterministic minimum spanning tree algorithm. (We give a constructive proof that the algorithmic complexity of the minimum spanning tree problem is equivalent to its decision-tree complexity.)   (2) An all-pairs shortest path algorithm for general graphs running in time O(mn + n 2 log log n) , where m and n are the number of edges and vertices. This provides the first improvement over approaches based on Dijkstra's algorithm.   (3) An all-pairs shortest path algorithm for undirected graphs running in O(mn log &alpha) time, where &alpha = &alpha(m,n) is the inverse-Ackermann function.   (4) A single-source shortest path algorithm running in O(m &alpha + min [ n log log r,  n log n ] ) time, where r bounds the ratio of any two edge lengths. For r polynomial in n this is O(m + n log log n) , an improvement over Dijkstra's algorithm.   (5) An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem. This is the first inverse-Ackermann type lower bound for a comparison-based problem.   (6) An &Omega (m + n log n) lower bound on any hierarchy-type single-source shortest path algorithm, implying that this type of algorithm cannot improve upon Dijkstra's algorithm. (All of our shortest path algorithms are of the hierarchy type.)   (7) The first parallel minimum spanning tree algorithm that is optimal w.r.t. to both time and work. Our algorithm is for the EREW PRAM model.   (8) A parallel, expected linear-work minimum spanning tree algorithm using only a polylogarithmic number of random bits.   (9) An O(mn log &alpha) bound on the comparison-addition complexity of all-pairs shortest paths. This is within a tiny   log &alpha factor of optimal when m = O(n) .

DOWNLOAD tr03-35.pdf

TR-03-33

Gorinsky, Sergey. "Robust Congestion Control for IP Multicast". The University of Texas at Austin, Department of Computer Sciences. Report# TR-03-33 (dissertation). August 2003. 124 pages.

IP multicast is a network service for scalable distribution of data to multiple receivers. Traditional protocols for multicast congestion control rely on trust: each party is assumed to follow guidelines for fair bandwidth sharing. However, with the growth and commercialization of the Internet, the assumption of universal trust is no longer tenable. In this dissertation, we consider a relaxed model where receivers are untrustworthy and can misbehave to acquire an unfairly high bandwidth at the expense of competing traffic. Our experiments with existing multicast protocols show that each of the evaluated protocols is vulnerable to receiver misbehavior. To take the first step towards robust multicast designs for distrusted environments, we focus on the class of feedback-free protocols where receivers provide no feedback to the sender and control congestion by regulating their subscription levels in the multi-group session. Unfortunately, the mechanism of group subscription offers a misbehaving receiver an opportunity to inflate its subscription level. Such inflated subscription attacks pose a major threat to fairness of bandwidth allocation. This dissertation is the first to solve the problem of inflated subscription. The presented designs rely on an insight that the ability of a receiver to access a multicast group should be tied with the congestion status of the receiver. First, we address individual attacks where a receiver inflates its subscription with no assistance from other receivers. Our solution guards access to multicast groups with dynamic keys and consists of two independent components: DELTA (Distribution of ELigibility To Access) - a novel method for in-band distribution of group keys to receivers that are eligible to access the groups according to the congestion control protocol, and SIGMA (Secure Internet Group Management Architecture) - a generic architecture for key-based group access at edge routers. DELTA and SIGMA require only minimal generic changes in the edge routers, do not alter the core of the network, and introduce no auxiliary servers. Then, we extend the design to protect multicast congestion control against inflated subscription of colluding receivers. To illustrate that integration with DELTA and SIGMA makes multicast protocols robust to inflated subscription and preserves other congestion control properties, we derive and evaluate robust adaptations of RLM and FLID-DL protocols.

DOWNLOAD tr03-33.pdf

AI02-295

McQuesten, Paul H. "Cultural Enhancement of Neuroevolution". The University of Texas at Austin, Department of Computer Sciences. Report# AI02-295 (dissertation). August 2002. 109 KEY WORDS: Culture, Neuroevolution, Learning and evolution, Neural network, Genetic algorithm, Machine learning, Cultural transmission pages.

Any transmission of behavior from one generation to the next via nongenetic means is a process of culture. Culture provides major advantages for survival in the biological world. This dissertation develops four methods that harness the mechanisms of culture to enhance the power of neuroevolution: culling overlarge litters, mate selection by complementary competence, phenotypic diversity maintenance, and teaching offspring to respond like an elder. The methods are efficient because they operate without requiring additional fitness evaluations, and because each method addresses a different aspect of neuroevolution, they also combine smoothly. The combined system balances diversity and selection pressure, and improves performance both in terms of learning speed and solution quality in sequential decision tasks.

DOWNLOAD UT-AI-TR-02-295.pdf

AI02-294

Bednar, James. "LEARNING TO SEE: GENETIC AND ENVIRONMENTAL INFLUENCES ON VISUAL DEVELOPMENT". The University of Texas at Austin, Department of Computer Sciences. Report# AI02-294 (dissertation). May 2002. 138 pages.

How can a computing system as complex as the human visual system be specified and constructed? Recent discoveries of widespread spontaneous neural activity suggest a simple yet powerful explanation: genetic information may be expressed as internally generated training patterns for a general-purpose learning system. The thesis presents an implementation of this idea as a detailed, large-scale computational model of visual system development. Simulations show how newborn orientation processing and face detection can be specified in terms of training patterns, and how postnatal learning can extend these capabilities. The results explain experimental data from laboratory animals, human newborns, and older infants, and provide concrete predictions about infant behavior and neural activity for future experiments. They also suggest that combining a pattern generator with a learning algorithm is an efficient way to develop a complex adaptive system.

DOWNLOAD UT-AI-TR-02-294.pdf

TR-02-71

Kolbly, Donovan. ": Extensible Language Implementation". The University of Texas at Austin, Department of Computer Sciences. Report# TR-02-71 (dissertation). December 2002. 177 pages.

This work presents several new approaches to the construction of extensible languages, and is the first system to combine local, dynamically extensible context-free syntax with the expressive power of meta-level procedures. The unifying theme of our system is that meaning should be computed relative to local context. We show how this theme is manifest in an implementation of a Scheme macro system which achieves hygienic macro expansion without rewriting. Additionally, our Scheme macro system makes available compile-time meta-objects for additional power in writing macros; macros that pattern match on compile-time types for optimization at macro-processing time are one example. This approach is currently in use in our RScheme implementation of Scheme. We also show the how this approach is applied to languages with conventional syntax, using Java as an example. We present a dynamically extensible parser based on the Earley parsing algorithm. This approach is practical as well as flexible; a straightforward implementation in C parses a 600-line (2777 token) file in about 44ms on an 866MHz Pentium III. We also describe a language extension framework that makes possible an extensible variant of Java, in which new syntax can be supplied by the casual programmer with only limited knowledge of the underlying compiler implementation or approach. This finally makes available to Java programmers the easy access to structured macro facilities that Lisp programmers find so powerful. Finally, we demonstrate this framework by constructing a deterministic finite automaton language extension to Java.

DOWNLOAD tr02-71.ps.gz

TR-02-70

Mittal, Neeraj. ": Techniques for Analyzing Distributed Computations". The University of Texas at Austin, Department of Computer Sciences. Report# TR-02-70 (dissertation). May 2002. 182 pages.

Inherent non-determinism in distributed programs and presence of multiple threads of control makes it difficult to write correct distributed software. Not surprisingly, distributed systems are particularly vulnerable to software faults. To build a distributed system capable of tolerating software faults, two important problems need to be addressed: fault detection and fault recovery . The fault detection problem requires finding a (consistent) global state of the computation that satisfies certain predicate ( e.g. , violation of mutual exclusion). To prevent a fault from causing any serious damage such as corrupting stable storage, it is essential that it be detected in a timely manner. However, we prove that detecting a predicate in 2-CNF, even when no two clauses contain variables from the same process, is an NP-complete problem. We develop a technique, based on computation slicing , to reduce the size of the computation and thus the number of global states to be examined for detecting a predicate. Slicing can be used to throw away the extraneous global states of the computation in an efficient manner, and focus on only those that are currently relevant for our purpose. To detect a fault, therefore, rather than searching the state-space of the computation, it is much more efficient to search the state-space of the slice. We identify several useful classes of predicates for which the slice can be computed efficiently. Our experimental results indicate that slicing can lead to an exponential reduction over existing techniques both in terms of time as well as space for fault detection. To recover from faults, we consider rollback recovery approach, which involves restoring the system to a previous state and then re-executing. We focus on rollback recovery using controlled re-execution , which is useful and effective for tolerating synchronization faults . Unlike other approaches which depend on chance and do not ensure that the re-execution is fault-free, the controlled re-execution method avoids synchronization faults during re-execution in a deterministic fashion. Specifically, it selectively adds synchronization dependencies during re-execution to ensure that the previously detected synchronization faults do not occur again. We provide efficient algorithms to solve the problem for two important classes of synchronization faults.

DOWNLOAD tr02-70.pdf

TR-02-69

Erdem, Esra. "Theory of Applications of Answer Set Programming". The University of Texas at Austin, Department of Computer Sciences. Report# TR-02-69 (dissertation). August 2002. 233 pages.

Answer set programming (ASP) is a new form of declarative logic programming. ASP interprets a logic program as a constraint on sets of literals, just as a propositional formula can be viewed as a constraint on assignments of truth values to atoms. The concept of an answer set was originally proposed as a semantics of negation as failure in Prolog. Instead of traditional Prolog systems, ASP uses answer set solvers. The input of Prolog consists of a logic program and a query, and Prolog computes answer substitutions; the input of an answer set solver is a logic program, and the solver computes the program's answer sets. The idea of ASP is to represent a given computational problem as a logic program whose answer sets correspond to solutions, and to use an answer set solver to find an answer set. We have investigated the application of ASP to several combinatorial search problems, including planning, wire routing, and phylogeny reconstruction. Planning is the problem of finding a sequence of actions that leads to a given goal. Wire routing is the problem of determining the physical locations of all wires interconnecting the circuit components on a chip. Phylogeny reconstruction is the problem of constructing and labeling an evolutionary tree for a set of taxa (taxonomic units), which describes the evolution of the taxa in that set from their most recent common ancestor. In our work on phylogeny reconstruction, we have generated several conjectures about the evolutionary history of Indo-European languages. The work on the use of ASP for planning has led us to the investigation of some theoretical questions related to answer sets. One is the problem of equivalent transformations of logic programs: under what conditions can we replace a program by an equivalent program that can be processed by an answer set solver more efficiently? Another problem is related to completion--a process that can translate a logic program into a set of formulas of classical logic. In some cases, the interpretations satisfying the completion of a program are also the answer sets for that program. In such cases, we can use propositional solvers--systems that compute a model of a given set of clauses--to find the program's answer sets. For some problems, propositional solvers are more efficient than answer set solvers. Therefore, we have investigated under what conditions we can use propositional solvers to find the program's answer sets.

DOWNLOAD tr02-69.pdf

TR-02-62

Mettu, Ramgopal R. "Approximation Algorithms for NP-Hard Clustering Problems". The University of Texas at Austin, Department of Computer Sciences. Report# TR-02-62 (dissertation). August 2002. 114 pages.

Given a set of n points and their pairwise distances, the goal of clustering is to partition the points into a "small" number of "related" sets. Clustering algorithms are used widely to manage, classify, and summarize many kinds of data. In this dissertation, we study the classic facility location and k-median problems in the context of clustering, and formulate and study a new optimization problem that we call the online median problem. For each of these problems, it is known to be NP-hard to compute a solution with cost less than a certain constant factor times the optimal cost. We give simple constant-factor approximation algorithms for the facility location, k-median, and online median problems with optimal or near-optimal time bounds. We also study distance functions that are "approximately" metric, and show that such distance functions allow us to obtain a faster online median algorithm and to generalize our analysis to other objective functions, such as that of the well-known k-means heuristic. Given n points, the associated interpoint distances and nonnegative point weights, and a nonnegative penalty for each point, the facility location problem asks us to identify a set of cluster centers so that the weighted average cluster radii and the sum of the cluster center penalties are both minimized. The k-median problem asks us to identify exactly k cluster centers while minimizing just the weighted average cluster radii. We give a simple greedy algorithm for the facility location problem that runs in O(n^2) time and produces a solution with cost at most 3 times optimal. For the k-median problem, we develop and make use of a sampling technique that we call "successive sampling," and give a randomized constant-factor approximation algorithm that runs in O(n(k+\log{n}+\log^2{n})) time. We also give an Omega(nk) lower bound on the running time of any randomized constant-factor approximation algorithm for the k-median problem that succeeds with even a negligible constant probability. In many settings, it is desirable to browse a given data set at differing levels of granularity (i.e., number of clusters). To address this concern, we formulate a generalization of the k-median problem that we call the online median problem. The online median problem asks us to compute an ordering of the points so that, over all i, when a prefix of length i is taken as a set of cluster centers, the weighted average radii of the induced clusters is minimized. We show that a natural generalization of the greedy strategy that we call "hierarchically greedy" yields an algorithm that produces an ordering such that every prefix of the ordering is within a constant factor of the associated optimal cost. Furthermore, our algorithm has a running time of Theta(n^2). Finally, we study the performance of our algorithms in practice. We present implementations of our k-median and online median algorithms; our experimental results indicate that our approximation algorithms may be useful in practice.

DOWNLOAD tr02-62.pdf

TR-02-52

Berger, Emery D. "Memory Management for High-Performance Applications". The University of Texas at Austin, Department of Computer Sciences. Report# TR-02-52 (dissertation). August 2002. 113 pages.

Memory managers are a source of performance and robustness problems for application software. Current general-purpose memory managers do not scale on multiprocessors, cause false sharing of heap objects, and systematically leak memory. Even on uniprocessors, the memory manager is often a performance bottleneck. General-purpose memory managers also do not provide the bulk deletion semantics required by many applications, including web servers and compilers. The approaches taken to date to address these and other memory management problems have been largely ad hoc. Programmers often attempt to work around these problems by writing custom memory managers. This approach leads to further difficulties, including data corruption caused when programmers inadvertently free custom-allocated objects to the general-purpose memory manager. In this thesis, we develop a framework for analyzing and designing high-quality memory managers. We develop a memory management infrastructure called heap layers that allows programmers to compose efficient memory managers from reusable and independently testable components. We conduct the first comprehensive examination of custom memory managers and show that most of these achieve slight or no performance improvements over a state-of-the-art general-purpose memory manager. Building on the knowledge gained in this study, we develop a hybrid memory management abstraction called reaps that combines the best of both approaches, allowing server applications to manage memory quickly and flexibly while avoiding memory leaks. We identify a number of previously unnoticed problems with concurrent memory management and analyze previous work in the light of these discoveries. We then present a concurrent memory manager called Hoard and prove that it avoids these problems.

DOWNLOAD tr02-52.pdf

TR-02-43

Sahni, Jasleen Kaur. "Scalable Network Architectures for Providing Per-flow Service Guarantees". The University of Texas at Austin, Department of Computer Sciences. Report# TR-02-43 (dissertation). August 2002. 153 pages.

NO ABSTRACT

DOWNLOAD tr02-43.pdf

TR-02-02

Jiménez, Daniel A. "Delay-Sensitive Branch Predictors for Future Technologies". The University of Texas at Austin, Department of Computer Sciences. Report# TR-02-02 (dissertation). May 2002. 165 pages.

Accurate branch prediction is an essential component of a modem, deeply pipelined microprocessors. Because the branch predictor is on the critical path for fetching instructions, it must deliver a prediction in a single cycle. However, as feature sizes shrink and clock rates increase, access delay will significantly decrease the size and accuracy of branch predictors that can be accessed in a single cycle. Thus, there is a tradeoff between branch prediction accuracy and latency. Deeper pipelines improve overall performance by allowing more aggressive clock rates, but some performance is lost due to increased branch misprediction penalties. Ironically, with shorter clock periods, the branch predictor has less time to make a prediction and might have to be scaled back to make it faster, which decreases accuracy and reduces the advantage of higher clock rates. We propose several methods for breaking the tradeoff between accuracy and latency in branch predictors. Our methods fall into two broad categories: hierarchical predictors using purely hardware implementations, and cooperative predictors that off-load some prediction work to the compiler. We describe hierarchical organizations that extend traditional predictors. We then describe a highly accurate branch predictor based on a neural learning technique. Using a hierarchical organization, this complex multi-cycle predictor can be used as a component of a fast delay-sensitive predictor. We introduce a novel cooperative branch predictor that off-loads most of the prediction work to the compiler with profiling. The compiler communicates profiled information to the microprocessor using extensions to the instruction set. This Boolean formula predictor has a small and fast hardware implementation, and will work in less than one cycle in even the smallest technologies with the most aggressive projected clock rates. Finally, we present another cooperative technique, branch path re-aliasing, that moves complexity off of the critical path for making a prediction and into the compiler; this technique increases accuracy by reducing destructive aliasing during the less critical update stage.

DOWNLOAD tr02-02.pdf

TR-01-58

Samoladas, Vasilis. "On Indexing Large Databases for Advanced Data Models". The University of Texas at Austin, Department of Computer Sciences. Report# TR-01-58 (dissertation). August 2001. 191 pages.

In the last decade, the relational data model has been extended in nu- merous ways, including geographic information systems, abstract data types and object models, constraint and temporal databases, and on-line analytical processing. We study the indexing requirements of these data models. In many cases, these requirements are ful lled by ecient techniques for multidimen- sional range search. Previous techniques for multidimensional range search, such as the R-tree and its variants, are based on ad hoc assumptions on the na- ture of the workloads they index, and have been known to su er from reduced scalability and robustness. We adopt an alternative approach; our study fo- cuses on techniques that provide worst-case performance guarantees, and thus overcome these deficiencies.

DOWNLOAD tr01-58.pdf

TR-01-54

Marshall, Dana T. "The Exploitation of Image Construction Data and Temporal/Image Coherence in Ray Traced Animation". The University of Texas at Austin, Department of Computer Sciences. Report# TR-01-54 (dissertation). May 2001. 120 pages.

This dissertation proposed an elegant and fast method that speeds the calculation of ray traced animated scenes constructed of convex objects by a combination of temporal and image coherence.

DOWNLOAD tr01-54.pdf

TR-01-53

Amla, Nina. "Efficient Model Checking for Timing Diagrams". The University of Texas at Austin, Department of Computer Sciences. Report# TR-01-53 (dissertation). May 2001. 144 pages.

NO ABSTRACT

DOWNLOAD tr01-53.pdf

TR-01-52

Camahort, Emilio. "4D Light-Field Modeling and Rendering". The University of Texas at Austin, Department of Computer Sciences. Report# TR-01-52 (dissertation). Spring 2001. 186 pages.

Image-based models have recently become an alternative to geometry-based models for computer graphics. They can be formalized as specializations of a more general model, the light field. The light field represents everything visible from any point in 3D space. In computer graphics the light field is modeled as a function that varies over the 4D space of oriented lines. Early models parameterize an oriented line by its intersection with two parallel planes, a parameterization that was inspired by holography. In computer graphics it introduces unnecessary biases that produce a rendering artifact called the disparity problem. We propose an alternative isotropic parameterization, the direction-and-point parameterization (DPP). We compare it to other parameterizations and determine whether they are view-independent, that is, invariant under rotations, translations and perspective projections. We show that no parameterization is view-independent, and that only the DPP introduces a single bias. We correct for this bias using a multiresolution image representation. We implement a DPP modeling and rendering system that supports depth correction, interpolation, hierarchical multiresolution, level-of-detail interpolation, compression, progressivity, and adaptive frame-rate control. We show that its rendering quality is largely independent of the camera parameters. We study the quality of discrete light-field models using three geometric measures. Two quantify discretization errors in the positional and directional parameters of light field. The third measure quantifies pixelation artifacts. We solve three open problems: (i) how to optimally choose planes for two-plane and DPP models, (ii) where to position the discretization windows within those planes, and (iii) how to choose optimal window resolutions. For a given amount of storage, we show that DPP models give the best overall quality representation for 4D light-field modeling and rendering. We demonstrate the application of 4D light-field models to holography. We generate a holographic stereogram based on both planar and isotropic representations. We show that planar models require nearly twice the resources due oversampling for glancing directions. Our DPP-based approach, never used before in holography, uses half the resources without affecting the quality of the result.

DOWNLOAD tr01-52.pdf

TR-01-44

Gunnels, John Andrew. "A Systematic Approach to the Design and Analysis of Linear Algebra Algorithms". The University of Texas at Austin, Department of Computer Sciences. Report# TR-01-44 (dissertation). December 2001. 131 pages.

Over the last two decades, much progress has been made in the area of the high-performance sequential and parallel implementation of dense linear algebra operations. At what time can we confidently state that we truly understand this problem area and what form might evidence in support of this assertion take? It is our thesis that if we focus this question on the software architecture of libraries for dense linear algebra operations, we can claim to have reached the point where, for a restricted class of problems, we understand this area. In this dissertation, we provide evidence in support of this assertion by outlining a systematic and partially automated approach to the derivation and high-performance implementation of a large class of dense linear algebra operations. We have arrived at a conclusion that the answer is to apply formal derivation techniques from Computing Science to the development of high-performance linear algebra libraries. The resulting approach has resulted in an aesthetically pleasing, coherent code that facilitates performance analysis, intelligent modularity, and the enforcement of program correctness via assertions. In this dissertation, we illustrate this observation by looking at the development of the Formal Linear Algebra Methods Environment (FLAME) for implementing linear algebra algorithms. We believe that traditional methods of implementation do not reflect the natural manner in which an algorithm is either classified or derived. To remedy this discrepancy, we propose the use of a small set of abstractions that can be used to design and implement linear algebra algorithms in a simple and straightforward manner. These abstractions may be expressed in a script language that can be compiled into efficient executable code. We extend this approach to parallel implementations without adding substantial complexity. It should also be possible to translate these scripts into analytical equations that reflect their performance profiles. These profiles may allow software designers to systematically optimize their algorithms for a given machine or to meet a particular resource goal. Given the more systematic approach to deriving and implementing algorithms that is facilitated by better abstraction and classification techniques, this sort of analysis can be shown to be systematically derivable and automated.

DOWNLOAD tr01-44.pdf

TR-01-14

Warshaw, Lane Bradley. "Facilitating Hard Active Database Applications". The University of Texas at Austin, Department of Computer Sciences. Report# TR-01-14 (dissertation). May 2001. 161 pages.

Active database technology enhances traditional databases with rules that are executed in response to database events. Tills enhancement promises exceptional returns. Useful applications of the technology include view maintenance, workflow, and real-time decision control systems. Unfortunately, penetration of active databases has largely been restricted to simple rule systems. This narrowed focus can be attributed to all explicit connection of the active rules to the underlying concurrency control system. Although tills explicit Connection provides a level of flexibility, it becomes semantically intractable in more complex applications. Furthermore, rule execution is computationally intensive. Since rules spawn the execution of many queries over the contents of the database. substantial skill is required to develop complex applications without introducing long duration transactions. This dissertation addresses three issues surrounding application development that inhibits the feasibility of active databases. First, a quantitative evaluation is performed on the semantics of VenusDB, a modular active database Ianguage that executes within the nested transaction model. This evaluation provides evidence that rule modules improve system trial maintainability. Second, the most general contribution of this dissertation is the identification and study of Log Monitoring Applications (LMAs). LMAs are expert system applications that analyze logs maintained in a database. This dissertation develops the formal execution semantics and correctness proofs of concurrency schemes for applications within the LMA class. The results show that only a minimal number of coupling modes are necessary for the database integration of hard rule systems obeying the LMA restrictions. Third, the architecture and evaluation of an active database optimizer is presented. This optimizer uses database statistics to optimize rules as well as suggest physical schema optimizations. The optimizer is integrated within VenueDB to improve system scalability.

DOWNLOAD tr01-14.pdf

TR-01-07

Pierce, Evelyn Tumlin. "Self-Adjusting Quorum Systems For Byzantine Fault Tolerance". The University of Texas at Austin, Department of Computer Sciences. Report# TR-01-07 (dissertation). March 2001. 76 pages.

The purpose of this work has been to design protocols for a data service that tolerates Byzantine server faults by shifting between multiple tolerance modes at run time, monitoring itself for faulty server behavior and dynamically adjusting its own tolerance capabilities accordingly. Our goal is a system that runs in an efficient low-fault mode most of the time, but can adjust itself to cope with new faults as they occur. Our approach is based on the masking quorum systems of Malkhi and Reiter. Like the protocols originally proposed for these systems, our techniques are relatively economical in that updates and reads need to be performed only at a subset ("quorum") of data servers, thus decreasing the workload on individual servers and simplifying the recovery process when failures occur. However, our protocols implement the following additional capabilities: 1. Strengthened read and write protocols for serializability of completed operations. 2. Protocols for dynamically adjusting the threshold (and thus quorum size) of threshold masking quorum systems in response to information about the number and/or probability of faults in the system. 3. Protocols for detecting Byzantine server behavior in threshold masking quorum systems. As a subsidiary goal, we have sought to make our methods not only effective against random faulty server behavior, but also resistant to sabotage by a deliberate adversary. To this end, we have limited our use of standard assumptions, such as independence of failures and a priori limits on the number of faults, that restrict the applicability of many Byzantine fault tolerance techniques to questions of security.

DOWNLOAD tr01-07.pdf

TR-00-38

Tarafdar, Ashis. "Software Fault Tolerance in Distributed Systems Using Controlled Re-Execution". The University of Texas at Austin, Department of Computer Sciences. Report# TR-00-38 (dissertation). August 2000. 145 pages.

Distributed applications are particularly vulnerable to synchronization faults. An important approach to tolerating synchronization faults is "rollback recovery", which involves restoring a previous state and re-executing. Existing rollback recovery methods depend on chance and cannot guarantee that synchronization faults do not recur during re-execution. We propose a new rollback recovery method, "controlled re-execution", based on selectively adding synchronizations during re-execution to ensure that synchronization faults do not recur. The controlled re-execution method gives rise to three interesting questions: How do we determine the synchronizations that ensure a safe re-execution? How do we monitor an application to detect faulty global conditions? How well does controlled re-execution perform in practice? The first part of the dissertation addresses the "predicate control" problem which takes a computation and a global property and adds synchronizations to the computation to maintain the property. We design efficient algorithms to solve the problem for many useful predicates, including disjunctive predicates and various types of mutual exclusion predicates. These predicates correspond to commonly encountered synchronization faults such as races. The second part of the dissertation investigates the "predicate detection" problem which involves determining whether a global property occurs in a computation. We address the problem for the useful class of conjunctive predicates and in the context of an "extended" model of computation that allows improved predicate detection over the conventional model. We show that, in general, the problem is NP-Complete. However, an efficient solution is demonstrated for the useful cases of "receive-ordered" and "send-ordered" computations. Further, this solution can be used to achieve an improved, though exponential, solution for the general problem. The third part of the dissertation involves an experimental study of the controlled re-execution method. We evaluate the controlled re-execution method in tolerating race faults and find that the extra tracing costs imposed are within tolerable limits and that it greatly enhanced the likelihood of recovery. We conclude that controlled re-execution is an effective and desirable method for tolerating races in long-running non-interactive distributed applications.

DOWNLOAD tr00-38.pdf

TR-00-37

Hewett, Micheal. "Computational Perceptual Attention". The University of Texas at Austin, Department of Computer Sciences. Report# TR-00-37 (dissertation). May 10, 2002. 80 pages.

This dissertation describes CPA, a general-purpose mechanism for expressing and implementing attention policies that control the allocation of resources among sensory processing tasks in a robot or other advanced intelligent system. A wide variety of attention policies can be expressed in this mechanism, which also supports soft real-time constraints on perceptual processing. Intelligent systems can become inundated with data, resulting in perceptual overload and a consequent inability to formulate a timely or appropriate response. Perceptual overload is often modulated by a perceptual attention mechanism that filters and prioritizes incoming data. Most existing attention mechanisms are tailored to the specific task the system is performing. A general-purpose attention mechanism must have a task-independent interface for controlling attention; support a heterogeneous set of sensors; support heterogeneous methods for processing sensor data; and support real-time throughput constraints. The CPA is a general-purpose attention mechanism that supports multimodal perceptual attention. Using it, an intelligent system can enact and control a variety of attention policies for any type or combination of sensor or sensor data. An intelligent system dynamically creates multiple heterogeneous perception tasks in accord with behavioral goals and installs them in the CPA. The CPA supports two general categories of perception tasks: detectors, which do not retain information between perception cycles; and trackers, which do. Perception tasks are prioritized using an attention policy and are executed using a priority-based scheduler. A wide range of attention policies can be expressed in this mechanism, including policies that dynamically modify perception priorities, policies in which emergency input overrides normal perception processing, and policies that dynamically change the level of resistance to perceptual distractions. Results show that perception intervals as short as 100 milliseconds can be achieved with a five-sensor robot under a variety of attention policies. Analysis of the system's performance under perceptual load shows that qualitatively different attention policies can be realized in the attention mechanism. We show that intelligent systems can use the CPA to implement the four primary characteristics of human perceptual attention: selective attention, sustained attention, divided attention, and top-down control.

DOWNLOAD tr00-37.pdf

TR-00-36

Adams, William Edward. "Untangling the Threads: Reduction for a Concurrent Object-Based Programming Model (Dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# TR-00-36 (dissertation). August 2000. 292 pages.

Reduction is a technique for simplifying reasoning about systems where a set of sequential executions, which we call `threads', are executed concurrently. In a concurrent execution, steps from different threads are interleaved. A reduction theorem shows that a concurrent execution is equivalent to an execution in which all the steps of a given thread appear contiguously. These steps can be replaced by a single step representing the complete execution of the thread. Applying reduction to each thread in turn, we reduce a concurrent execution to a sequence of atomic steps, one for each thread. This is a sequential execution, where threads execute one at a time. Reasoning about the sequential reduction is significantly simpler than reasoning about the original execution. In the sequential execution, we do not need to consider the interactions of steps from different threads. We describe a model for concurrent systems, called `Seuss'. In this model, a program is a set of independently executing boxes, which communicate using a form of remote procedure call. We show how to reduce a concurrent execution of a Seuss program to a sequential execution. Since every concurrent execution is equivalent to a sequential execution, we can understand all possible executions of a Seuss program by understanding just its sequential executions. We show three main results. One gives sufficient conditions to guarantee that all threads in an execution terminate. The other two concern reduction of executions in which all threads terminate. We express the reduction results relative to restrictions on which pairs of threads can run concurrently. The first reduction theorem shows a restriction on concurrency that guarantees that every execution can be reduced to a sequential execution. The second reduction theorem gives a stronger restriction on concurrency (so less concurrency is allowed in an execution), but, in return, gives a reduced sequential execution that has stronger fairness properties (and thus better progress properties) than we get with the first theorem. To show these results, we use an operational semantics for a simple Seuss language. The semantics is such that our results apply to any language implementing the Seuss model.

DOWNLOAD tr00-36.pdf

TR-00-35

Gao, Youxin. "Interconnect Optimization in Deep Sub-micron Design under the Transmission Line Model". The University of Texas at Austin, Department of Computer Sciences. Report# TR-00-35 (dissertation). March 2001. 127 pages.

As the VLSI technology has been scaled down to 0.18nm in recent years and is expected to be scaled down to 0.05nm in the near future, interconnect delay becomes an important factor in achieving high performance. In deep sub-micron design, interconnect delay is shown to be 10 to a few hundred times bigger than the intrinsic gate delay for a global interconnect, and thus dominates the circuit delay. To reduce interconnect delay, wire-sizing and buffer insertion/sizing are two effective techniques. One of the approaches to wire-sizing is continuous wire-sizing. In continuous wire-sizing, the shape of a wire is described by a continuous function, and the objective is to find a shape function which minimizes delay or minimizes area subject to a delay bound. In the first part of this dissertation, we present some continuous wire-sizing results under the Elmore delay model. In the second part of this dissertation, we present some wire-sizing results under the transmission line model. In the third part of this dissertation, we present a graph based algorithm for optimal buffer insertion under accurate delay models.

DOWNLOAD tr00-35.pdf

AI99-278

Thompson, Cynthia A. "Semantic Lexicon Acquisition for Learning Natural Language Interfaces". The University of Texas at Austin, Department of Computer Sciences. Report# AI99-278 (dissertation). February 23, 1999. 87 pages.

A long-standing goal for the field of artificial intelligence is to enable computer understanding of human languages. A core requirement in reaching this goal is the ability to transform individual sentences into a form better suited for computer manipulation. This ability, called semantic parsing, requires several knowledge sources, such as a grammar, lexicon, and parsing mechanism. Building natural language parsing systems by hand is a tedious, error-prone undertaking. We build on previous research in automating the construction of such systems using machine learning techniques. The result is a combined system that learns semantic lexicons and semantic parsers from one common set of training examples. The input required is a corpus of sentence/representation pairs, where the representations are in the output format desired. A new system, WOLFIE, learns semantic lexicons to be used as background knowledge by a previously developed parser acquisition system, CHILL. The combined system is tested on a real world domain of answering database queries. We also compare this combination to a combination of CHILL with a previously developed lexicon learner, demonstrating superior performance with our system. In addition, we show the ability of the system to learn to process natural languages other than English. Finally, we test the system on an alternate sentence representation, and on a set of large, artificial corpora with varying levels of ambiguity and synonymy. One difficulty in using machine learning methods for building natural language interfaces is building the required annotated corpus. Therefore, we also address this issue by using active learning to reduce the number of training examples required by both WOLFIE and CHILL. Experimental results show that the number of examples needed to reach a given level of performance can be significantly reduced with this method.

DOWNLOAD UT-AI-TR-99-278.pdf

TR-99-10

Chen, Chung-Ping. "Performance-Driven Interconnect Optimization (dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# TR-99-10 (dissertation). August 1998. 141 pages.

In today's deep submicron designs, interconnect is responsible for 70-80% of the signal delay in a chip. This is in sharrp contrast to the situation of just a few years ago, when gate delay was the dominant factor in determining circuit performance, and when interconnect was essentially treated as a delay-free metal wire. If deep submicron integrated circuits are to excel in yield and performance, the design process must focus on interconnects. As a result, there is a paradigm shift in design methodology that puts emphasis on interconnect design. Wire sizing, buffer sizing, and buffer insertion are effective techniques to optimize interconnect performance and signal integrity. In this thesis, we present the results on interconnect optimization based on these techniques.

DOWNLOAD tr99-10.pdf

TR-99-07

Puchol, Carlos. "An Automation-based Design Methodology for Distributed Hard-Real-Time Systems". The University of Texas at Austin, Department of Computer Sciences. Report# TR-99-07 (dissertation). February 1999. 181 pages.

Despite significant progress in realtime systems design in recent years, most research has concentrated on some specific areas such as scheduling, timing analysis or specification. This thesis focuses on the proper definition of the global structure of a realtime system, what it is and and how to integrate all its aspects towards obtaining a complete design that satisfies the specification. In this thesis, we consider the problem of providing a general, integrated, and highly automated framework for the design of distributed hardrealtime systems which combines and exploits analytical techniques from individual areas of research. We propose such a framework, which may be thought of as providing a design methodology for the domain of realtime systems. Our proposed methodology is based on three fundamental principles: automation, formalization and generality. We propose a specification language based on these notions and developed from insight on the semantics and experience of the Modechart language (a specification language for realtime systems), also included in this dissertation. Current practice in the design and implementation realtime systems is a largely ad hoc process of trial and error. Our design methodology, separates the concerns involved and provides an environment which allows a designer to systematically meet the design constraints. This is achieved by providing language support to capture highlevel designs and to generate code automatically from them, that, together with the methodoligy presented and the application specific code, is designed to satisfy the realtime requirements. We present Modechart++, which supports the design methodology introduced and it is used to specify, verify, and synthesize code for distributed hardrealtime applications.

DOWNLOAD tr99-07.pdf

TR-99-06

Namjoshi, Kedar Sharad. "Ameliorating the State Explosion Problem". The University of Texas at Austin, Department of Computer Sciences. Report# TR-99-06 (dissertation). February 1999. 155 pages.

Systems that maintain an ongoing interaction with their environment, such as Operating Systems Network Protocols and Microcontrollers, are commonplace. The complexity of these systems necessitates a rigorous verification of correct behavior. Automatic verification methods such as Model Checking, while theoretically efficient, suffer in practice from the large state space of these systems, a phenomenon called State Explosion. State explosion often arises when verifying systems parameterized by the number of component processes, and single systems with large data domains. The main contribution of this dissertation is in the development of abstraction methods that serve to ameliorate the state explosion problem for such systems. The first part of the dissertation presents abstractions for interesting classes of parameterized systems that reduce the infinite family of instances to a finite-state system, while exactly preserving correctness properties. For parameterized ring systems with a synchronizing token, it suffices to examine a few small instances in order to determine the correctness of every instance of the system. The method is applicable to protocols such as mutual exclusion and Milner's Cycler. Somewhat surprisingly, the verification problem is undecidable even if the token carries a single bit of information. For parameterized synchronous systems, an exact abstraction reduces the parameterized system to a finite "abstract" graph. This abstraction method is applied to the verification of the SAEJ1850 industrial standard bus arbitration protocol. We also present a general algorithm schema from which algorithms for model-checking several types of infinite-state systems can be derived. The second part of the dissertation presents a proof technique for showing that two programs are equivalent up to "stuttering" (repetition) of states. Stuttering arises when comparing programs that are at different levels of abstraction. The new formulation replaces the global reasoning of earlier techniques with local reasoning, which considerably simplifies abstraction proofs. This new formulation is used in conjunction with a theorem prover to verify a data abstraction for the alternating-bit protocol.

DOWNLOAD tr99-06.pdf

AI98-265

Ramachandran, Sowmya. "Theory Refinement of Bayesian Networks with Hidden Variables". The University of Texas at Austin, Department of Computer Sciences. Report# AI98-265 (dissertation). May 1998. 129 pages.

Research in theory refinement has shown that biasing a learner with initial, approximately correct knowledge produces more accurate results than learning from data alone. While techniques have been developed to revise logical and connectionist representations, little has been done to revise probabilistic representations. Bayesian networks are well-established as a sound formalism for representing and reasoning with probabilistic knowledge, and are widely used. There has been a growing interest in the problem of learning Bayesian networks from data. However, there is no existing technique for learning or revising Bayesian networks with hidden variables (i.e. variables not represented in the data), that has been shown to be efficient, effective, and scalable through evaluation on real data. The few techniques that exist for revising such networks perform a blind search through a large space of revisions, and are therefore computationally expensive. This dissertation presents Banner, a technique for using data to revise a given Bayesian network with Noisy-Or and Noisy-And nodes, to improve its classification accuracy. Additionally, the initial network can be derived directly from a logical theory expressed as propositional Horn-clause rules. Banner can revise networks with hidden variables, and add hidden variables when necessary. Unlike previous approaches to this problem, Banner employs mechanisms similar to those used in logical theory refinement techniques for using the data to focus the search for effective modifications to the network. It can also be used to learn networks with hidden variables from data alone. We also introduce Banner-Pr, a technique for revising the parameters of a Bayesian network with Noisy-Or/And nodes, that directly exploits the computational efficiency afforded by these models. Experiments on several real-world learning problems in domains such as molecular biology and intelligent tutoring systems demonstrate that Banner can effectively and efficiently revise networks to significantly improve their accuracies, and thus learn highly accurate classifiers. Comparisons with the Naive Bayes algorithm show that using the theory refinement approach gives Banner a substantial edge over learning from data alone. We also show that Banner-Pr converges faster and produces more accurate classifiers than an existing algorithm for learning the parameters of a network.

DOWNLOAD UT-AI-TR-98-265.pdf

AI98-269

Estlin, Tara Adrienne. "Using Multi-Strategy Learning to Improve Planning Efficiency and Quality". The University of Texas at Austin, Department of Computer Sciences. Report# AI98-269 (dissertation). May 1998. 117 pages.

Artificial intelligence planning systems have become an important tool for automating a wide variety of tasks. However, even the most current planning algorithms suffer from two major problems. First, they often require infeasible amounts of computation time to solve problems in most domains. And second, they are not guaranteed to return the best solution to a planning problem, and in fact can sometimes return very low-quality solutions. One way to address these problems is to provide a planning system with domain-specific control knowledge, which helps guide the planner towards more promising search paths. Machine learning techniques enable a planning system to automatically acquire search-control knowledge for different applications. A considerable amount of planning and learning research has been devoted to acquiring rules that improve planning efficiency, also known as speedup learning. Much less work has been down in learning knowledge to improve the quality of plans, even though this is an essential feature for many real-world planning systems. Furthermore, even less research has been done in acquiring control knowledge to improve both these metrics. The learning system presented in this dissertation, called SCOPE, is a unique approach to learning control knowledge for planning. SCOPE learns domain-specific control rules for a planner that improve both planning efficiency and plan quality, and it is one of the few systems that can learn control knowledge for partial-order planning. SCOPE's architecture integrates explanation-based learning (EBL) with techniques from inductive logic programming. Specifically, EBL is used to constrain an inductive search for control heuristics that help a planner choose between competing plan refinements. Since SCOPE uses a very flexible training approach, its learning algorithm can be easily focused to prefer search paths that are better for particular evaluation metrics. SCOPE is extensively tested on several planning domains, including a logistics transportation domain and a production manufacturing domain. In these tests, it is shown to significantly improve both planning efficiency and quality and is shown to be more robust than a competing approach.

DOWNLOAD UT-AI-TR-98-269.pdf

AI98-276

Califf, Mary Elaine. "Relational Learning Techniques for Natural Language Extraction". The University of Texas at Austin, Department of Computer Sciences. Report# AI98-276 (dissertation). August 1998. 132 pages.

The recent growth of online information available in the form of natural language documents creates a greater need for computing systems with the ability to process those documents to simplify access to the information. One type of processing appropriate for many tasks is information extraction, a type of text skimming that retrieves specific types of information from text. Although information extraction systems have existed for two decades, these systems have generally been built by hand and contain domain specific information, making them difficult to port to other domains. A few researchers have begun to apply machine learning to information extraction tasks, but most of this work has involved applying learning to pieces of a much larger system. This dissertation presents a novel rule representation specific to natural language and a relational learning system, Rapier, which learns information extraction rules. Rapier takes pairs of documents and filled templates indicating the information to be extracted and learns pattern-matching rules to extract fillers for the slots in the template. The system is tested on several domains, showing its ability to learn rules for different tasks. Rapier's performance is compared to a propositional learning system for information extraction, demonstrating the superiority of relational learning for some information extraction tasks. \\ Because one difficulty in using machine learning to develop natural language processing systems is the necessity of providing annotated examples to supervised learning systems, this dissertation also describes an attempt to reduce the number of examples Rapier requires by employing a form of active learning. Experimental results show that the number of examples required to achieve a given level of performance can be significantly reduced by this method.

DOWNLOAD UT-AI-TR-98-276.pdf

TR-98-17

John, Ajita. "Compilation of Constraint Systems to Parallel Procedural Programs (dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# TR-98-17 (dissertation). September 1998. 124 pages.

This dissertation reports on the compilation of constraint systems into task level parallel programs in a procedural language. This is the only research, of which we are aware, which attempts to generate efficient parallel programs for numerical computations from constraint systems. Computations are expressed as constraint systems. A dependence graph is derived from the constraint system and a set of input variables. The dependence graph, which exploits the parallelism in the constraints, is mapped to the target language CODE, which represents parallel computation structures as generalized dependence graphs. Finally, parallel C programs are generated. To extract parallel programs of appropriate granularity, the following features have been included. (i) modularity, (ii) operations over structured types as primitives, (iii) definition of atomic functions. A prototype compiler has been implemented. The execution environment or software architecture is specified separately from the constraint system. The domain of matrix computations has been targeted for applications. Performance results for example programs are very encouraging. The feasibility of extracting efficient and portable parallel programs from domain-specific constraint systems has been established.

DOWNLOAD tr98-17.pdf

TR-98-07

Kakkad, Sheetal V. "Address Translation and Storage Management for Persistent Object Stores". The University of Texas at Austin, Department of Computer Sciences. Report# TR-98-07 (dissertation). March 1998. 219 pages.

A common problem in software engineering is efficiently saving the state of application data structures to non-volatile storage between program executions. If this is accomplished using normal file systems, the programmer is forced to explicitly save the data to files as a stream of uninterpreted bytes, thereby losing both pointer semantics and object identity. A better approach is to use persistent object storage, a natural extension to virtual memory that allows heap data to be saved automatically to disk while maintaining the topology of data structures without any explicit programmer intervention. If persistent object stores are to replace the functionality of normal file systems, they must be able to address large volumes of data efficiently on standard hardware. High-performance address translation techniques are necessary and important for supporting large address spaces on stock hardware. We present pointer swizzling at page fault time (PS@PFT), a coarse-grained address translation scheme suitable for this purpose, and demonstrate it by building a persistent storage system for C++ called the Texas Persistent Store. We also discuss alternative approaches for portably incorporating fine-grained address translation in Texas for situations where coarse-grained swizzling alone is insufficient. As part of the performance results, we present a detailed analysis of various components of a coarse-grained address translation technique, including a comparison with overall I/O costs. Pointer swizzling requires run-time knowledge of in-memory object layouts to locate pointers in objects. We have developed and implemented Run-Time Type Description (RTTD) for this purpose; our implementation strategy is portable because it is based on a novel use of compiler-generated debugging information for extracting the necessary type description. RTTD is also useful for other applications such as data structure browsing, and advanced profiling and tracing. Another part of this research is a study of the interaction between systems similar to PS@PFT and operating systems, particularly regarding virtual memory management issues. We suggest areas where operating system implementations can be made more open to improve their performance and extensibility. Finally, we briefly discuss storage management issues, specifically log-structured storage, disk prefetching, and compressed in-memory storage, and provide directions for future research in this area.

DOWNLOAD tr98-07.pdf

AI97-257

Moriarty, David E. "Symbiotic Evolution of Neural Networks in Sequential Decision Tasks". The University of Texas at Austin, Department of Computer Sciences. Report# AI97-257 (dissertation). January 1997. 115 pages.

Sequential decision tasks appear in many practical situations ranging from robot navigation to stock market trading. Because of the complexity of such tasks, it is often difficult to perceive the direct consequences of individual decisions and even harder to generate examples of correct behavior. Consequently, difficult decision problems such as routing traffic, autonomous control, and resource allocation are often unautomated or are only semi-automated using ``rule-of-thumb'' strategies or simple heuristics. This dissertation proposes a general methodology for automating these tasks using techniques from machine learning. Specifically, this research studies the combination of evolutionary algorithms and artificial neural networks to learn and perform difficult decision tasks. Evolutionary algorithms provide an efficient search engine for building decision strategies and require only minimal reinforcement or direction from the environment. Neural networks provide an efficient storage mechanism for the decision policy and can generalize experiences from one situation to another. The learning system developed in this dissertation called SANE contains an evolutionary algorithm specifically tailored to sequential decision learning. Populations evolve faster than previous methods and rarely converge on suboptimal solutions. SANE is extensively evaluated and compared to existing decision learning systems and other evolutionary algorithms. SANE is shown to be significantly faster, more robust, and more adaptive in almost every situation. Moreover, SANE's efficient searches return more profitable decision strategies. The flexibility and scope of SANE is demonstrated in two real-world applications. First, SANE significantly improves the play of a world champion Othello program. Second, SANE successfully forms neural networks that guide a robot arm to target objects while avoiding randomly placed obstacles. The contributions of this research are twofold: a novel integration of evolutionary algorithms and neural networks and an efficient system for learning decision strategies in complex problems.

DOWNLOAD UT-AI-TR-97-257.pdf

AI97-261

Hermjakob, Ph.D., Ulf. "Learning Parse and Translation Decisions From Examples With Rich Context". The University of Texas at Austin, Department of Computer Sciences. Report# AI97-261 (dissertation). May 1997. 265 pages.

The parsing of unrestricted text, with its enormous lexical and structural ambiguity, still poses a great challenge in natural language processing. The difficulties with traditional approaches, which try to master the complexity of parse grammars with hand-crafted rules, have led to a trend towards more empirical techniques. We therefore propose a system for parsing and we choose a deterministic shift-reduce type parser that integrates part-of-speech tagging and syntactic and semantic processing, which not only makes parsing very efficient, but also assures transparency during the supervised example acquisition. Applying machine learning techniques, the system uses parse action examples to generate a parser in the form of a decision structure, a generalization of decision trees. To learn good parsing and translation decisions, our system relies heavily on context, as encoded in currently 205 features describing the morphological, syntactical and semantical aspects of a given parse state. Compared with recent probabilistic systems that were trained on 40,000 sentences, our system relies on more background knowledge and a deeper analysis, but radically fewer examples, currently 256 sentences. We test our parser on lexically limited sentences from the Wall Street Journal and achieve accuracy rates of 89.8% for labeled precision, 98.4% for part of speech tagging and 56.3% of test sentences without any crossing brackets. Machine translations of 32 Wall Street Journal sentences to German have been evaluated by 10 bilingual volunteers and been graded as 2.4 on a 1.0 (best) to 6.0 (worst) scale for both grammatical correctness and meaning preservation. The translation quality was only minimally better (2.2) when starting each translation with the correct parse tree, which indicates that the parser is quite robust and that its errors have only a moderate impact on final translation quality. These parsing and translation results already compare well with other systems and, given the relatively small training set and amount of overall knowledge used so far, the results suggest that our system CONTEX can break previous accuracy ceilings when scaled up further.

DOWNLOAD UT-AI-TR-97-261.pdf

AI97-264

Clancy, Daniel Joseph. "Solving Complexity and Ambiguity Problems in Qualitative Simulation". The University of Texas at Austin, Department of Computer Sciences. Report# AI97-264 (dissertation). December 1997. 218 pages.

Qualitative simulation is used to reason about the behavior of imprecisely defined dynamical systems for tasks such as monitoring, diagnosis, or design. Often, however, simulation of complex dynamical systems results in either an intractable simulation or an ambiguous behavioral description. These results have caused concern regarding the scalability of techniques based upon qualitative simulation to real--world problems. Two different approaches are used to solve these problems: 1) abstraction and problem decomposition techniques are used during simulation to focus on relevant distinctions thus reducing the overall complexity of the simulation; and 2) the expressiveness of the modeling language is extended to allow the modeler to incorporate additional information. Model decomposition and simulation (DecSIM) uses a component--based simulation algorithm to reason about the complex interactions within a sub--system independent of the interactions between subsystems. Variables within the model are partitioned into closely related components and a separate behavioral description is generated for each component. Links are maintained between related components to ensure that all of the constraints in the model are satisfied. DecSIM results in exponential speed--up for models that lend themselves to decomposition. Furthermore, DecSIM is guaranteed to generate a behavioral description that is equivalent to the description generated by a standard QSIM simulation modulo the temporal ordering of events for variables in separate components. A common source of irrelevant distinctions within qualitative simulation is intractable branching due to chatter. Chatter occurs when the derivative of a variable is constrained only by continuity within a restricted region of the state space. We present two different abstraction techniques that completely eliminate the problem of chatter by abstracting a chattering region into a single abstract state. Both techniques retain the QSIM soundness guarantee and eliminate all instances of chatter without over--abstracting. To address the problem of an ambiguous behavioral description, Temporally Constrained QSIM (TeQSIM) integrates temporal logic model checking into the qualitative simulation process allowing the modeler to specify behavioral information via trajectory constraints. Trajectory constraints, specified using an extension of a propositional linear--time temporal logic, can be used to focus the simulation, simulate non--autonomous systems and reason about boundary condition problems.

DOWNLOAD UT-AI-TR-97-264.pdf

TR-97-29

Johnstone, Mark Stuart, B.S., M.S. "Non-Compacting Memory Allocation and Real-Time Garbage Collection". The University of Texas at Austin, Department of Computer Sciences. Report# TR-97-29 (dissertation). December 1997. 442 pages.

Dynamic memory management is a very important feature of modern programming languages, and one that is often taken for granted. Programmers frequently place great demands on the memory management facilities of their language, and expect the language to efficiently handle these requests. Unfortunately, memory management systems are not always up to the task. The article which appears below strikingly illustrates how problems with a program's dynamic memory management can cause disastrous results, sometimes years after the program is written. Memory errors like this one are very difficult to prevent, and it is a certainty that they will occur again and again. It is our hope that the results presented in this research will lead to a better under standing of the nature of memory management problems, and to improved implementations of memory management systems . We believe that improved memory management systems will ultimately lead to more robust software, and problems like the one presented in the following article will become a rare exception rather than the rule.

DOWNLOAD tr97-29.pdf

TR-97-25

McCain, Norman Clayton. "Causality in Commonsense Reasoning about Actions". The University of Texas at Austin, Department of Computer Sciences. Report# TR-97-25 (dissertation). September 1997. 210 pages.

In this dissertation, we investigate the role of causal knowledge in commonsense reasoning about action and change. We define a language in which a relatively simple form of causal knowledge is expressed. Using this language, we describe a novel approach to formalizing action domains as "causal theories" including domains that involve concurrency, nondeterminism, and things that change by themselves. We show that a subclass of causal theories can be translated into propositional logic by a generalization of Clark's completion procedure for logic programs. Finally, we describe an implemented approach to automated query answering and "satisfiability planning" which is based on this translation.

DOWNLOAD tr97-25.pdf

TR-97-24

Rajaraman, Rajmohan. "Sharing Resources in Distributed Systems". The University of Texas at Austin, Department of Computer Sciences. Report# TR-97-24 (dissertation). December 1997. 226 pages.

An important goal of a distributed system is to effectively utilize the collective resources of the system, namely, the memory and the processors of the individual nodes. This dissertation addresses certain problems pertaining to sharing memory and processors in distributed systems. In the first part of the dissertation, we study two important issues that arise while sharing memory in a distributed system: memory contention and faults. We adopt a model of computation in which each node can send or receive at most a constant number of objects per step. Our main result is a simple protocol for providing fast access to shared objects in an environment in which memory contention is unconstrained and a constant fraction of the nodes and communication links may be faulty at any time. Our protocol combines techniques for hashing and erasure codes with a new mechanism for on-line replication. We show that if each new access request is chosen according to a fixed probability distribution over the set of objects, then our protocol rapidly reaches a steady state in which each request is satisfied in an expected constant number of steps and the throughput of the protocol is asymptotically optimal. We also prove that the protocol continues to remain in a steady state if changes in the access pattern are moderate. The second part of the dissertation studies load balancing, which is a mechanism for sharing processors in a distributed system. We analyze the effectiveness of a local load balancing algorithm in which each node repeatedly balances its load with its neighbors. Our main results concern the static version of the problem where we assume that the total load does not change with time. We analyze the local balancing algorithm in terms of both the imbalance of the initial load distribution and several parameters of the network, including the number of nodes, the maximum degree, and the edge expansion. We show that the algorithm is worst-case optimal for all networks. We improve this result for the special case of ring networks by showing that the local balancing approach is optimal (up to an additive linear term) for every initial distribution of load on the ring. Our results are also shown to hold for an asynchronous model of computation. This dissertation demonstrates that a number of basic resource sharing problems admit efficient solutions in the form of simple local algorithms. Our algorithms are simple in the sense that the program running at each node can be expressed as a periodic process that repeatedly executes a small number of fixed operations. Our algorithms are local in the sense that each node either communicates with only its nearest neighbors or sends messages to only a small number of other nodes.

DOWNLOAD tr97-24.pdf

TR-97-12

Hermjakob, Ulf. "Learning Parse and Translation Decisions From Examples With Rich Context". The University of Texas at Austin, Department of Computer Sciences. Report# TR-97-12 (dissertation). July 1997. 165 pages.

The parsing of unrestricted text, with its enormous lexical and structural ambiguity, still poses a great challenge in natural language processing. The difficulties with traditional approaches, which try to master the complexity of parse grammars with hand-crafted rules, have led to a trend towards more empirical techniques. We therefore propose a system for parsing and translating natural language that learns from examples and uses some background knowledge. As our parsing model we choose a deterministic shift-reduce type parser that integrates part-of-speech tagging and syntactic and semantic processing, which not only makes parsing very efficient, but also assures transparency during the supervised example acquisition. Applying machine learning techniques, the system uses parse action examples to generate a parser in the form of a decision structure, a generalization of decision trees. To learn good parsing and translation decisions, our system relies heavily on context, as encoded in currently 205 features describing the morphological, syntactical and semantical aspects of a given parse state. Compared with recent probabilistic systems that were trained on 40,000 sentences, our system relies on more background knowledge and a deeper analysis, but radically fewer examples, currently 256 sentences. We test our parser on lexically limited sentences from the Wall Street Journal and achieve accuracy rates of 89.8% for labeled precision, 98.4% for part of speech tagging and 56.3% of test sentences without any crossing brackets. Machine translations of 32 Wall Street Journal sentences to German have been evaluated by 10 bilingual volunteers and been graded as 2.4 on a 1.0 (best) to 6.0 (worst) scale for both grammatical correctness and meaning preservation. The translation quality was only minimally better (2.2) when starting each translation with the correct parse tree, which indicates that the parser is quite robust and that its errors have only a moderate impact on final translation quality. These parsing and translation results already compare well with other systems and, given the relatively small training set and amount of overall knowledge used so far, the results suggest that our system Contex can break previous accuracy ceilings when scaled up further.

DOWNLOAD tr97-12.pdf

TR-97-03

Hsu, Tsan-sheng. "Graph Augmentation and Related Problems: Theory and Practice". The University of Texas at Austin, Department of Computer Sciences. Report# TR-97-03 (dissertation). January 24, 1997. 346 pages.

Graphs play an important role in modeling the underlying structure of many real world problems. In this thesis, we investigate several interesting graph problems. The first part of this thesis focuses on the problem of finding a smallest set of edges whose addition makes an input undirected graph satisfy a given connectivity requirement. This is a fundamental graph theoretic problem that has a wide variety of applications in designing reliable networks and database systems. We have obtained efficient sequential and parallel algorithms for finding smallest augmentations to satisfy 3-edge-connectivity, 4-edge-connectivity, biconnectivity, triconnectivity, and four-connectivity. Our parallel algorithms are developed on the PRAM model. Our approach in obtaining these results is to first construct a data structure that describes all essential information needed to augment the input graph, e.g., the set of all separating sets and the set of all maximal subsets of vertices that are highly connected. Based on this data structure, we obtain a lower bound on the number of edges that need to be added and prove that this lower bound can be always reduced by one by properly adding an edge. The second part of the thesis focuses on the implementation of PRAM-based efficient parallel graph algorithms on a massively parallel SIMD computer. This work was performed in two phases. In the first phase, we implemented a set of parallel graph algorithms with the constraint that the size of the input cannot be larger than the number of physical processors. For this, we first built a kernel which consists of commonly used routines. Then we implemented efficient parallel graph algorithms by calling routines in the kernel. In the second phase, we addressed and solved the issue of allocating virtual processors in our programs. Under our current implementation scheme, there is no bound on the number of virtual processors used in the programs as long as there is enough memory to store all the data required during the computation. The performance data obtained from extensive testing suggests that the extra overhead for simulating virtual processors is moderate and the performance of our code tracks theoretical predictions quite well.

DOWNLOAD tr97-03.pdf

AI96-249

Zelle, John Marvin, Ph.D. "Using Inductive Logic Programming to Automate the Construction of Natural Language Parsers". The University of Texas at Austin, Department of Computer Sciences. Report# AI96-249 (dissertation). December 1995. 121 pages.

Designing computer systems to understand natural language input is a difficult task. In recent years there has been considerable interest in corpus-based methods for constructing natural language parsers. These empirical approaches replace hand-crafted grammars with linguistic models acquired through automated training over language corpora. A common thread among such methods to date is the use of propositional or probabilistic representations for the learned knowledge. This dissertation presents an alternative approach based on techniques from a subfield of machine learning known as inductive logic programming (ILP). ILP, which investigates the learning of relational (first-order) rules, provides an empirical method for acquiring knowledge within traditional symbolic parsing frameworks. This dissertation details the architecture, implementation and evaluation of CHILL, a computer system for acquiring natural language parsers by training over corpora of parsed text. CHILL treats language acquisition as the learning of search-control rules within a logic program that implements a shift-reduce parser. Control rules are induced using a novel ILP algorithm which handles difficult issues arising in the induction of search-control heuristics. Both the control-rule framework and the induction algorithm are crucial to CHILL'S success. The main advantage of CHILL over propositional counterparts is its flexibility in handling varied representations. CHILL has produced parsers for various analyses including case-role mapping, detailed syntactic parse trees, and a logical form suitable for expressing first-order database queries. All of these tasks are accomplished within the same framework, using a single, general learning method that can acquire new syntactic and semantic categories for resolving ambiguities. Experimental evidence from both artificial and real-world corpora demonstrates that CHILL learns parsers as well or better than previous artificial neural network or probabilistic approaches on comparable tasks. In the database query domain, which goes beyond the scope of previous empirical approaches, the learned parser outperforms an existing hand-crafted system. These results support the claim that ILP techniques as implemented in CHILL represent a viable alternative with significant potential advantages over neural-network, propositional, and probabilistic approaches to empirical parser construction.

DOWNLOAD NOT AVAILABLE

AI96-254

Lee, Wan Yik. "Spatial Semantic Hierarchy for a Physical Mobile Robot". The University of Texas at Austin, Department of Computer Sciences. Report# AI96-254 (dissertation). December 1996. 160 pages.

This dissertation describes research to extend and improve the Spatial Semantic Hierarchy (SSH) approach to robot exploration and mapping, and to demonstrate and evaluate its effectiveness in controlling physical mobile robots. The SSH approach for robot exploration and mapping was first developed in the context of a simulated robot, NX, and tested in simulated environments with very simple models of sensorimotor error. Physical implementations of aspects of the SSH approach have been built by other researchers but they do not provide an adequate demonstration of its strengths or an adequate analysis of its conditions of applicability. The dissertation work extended and improved the SSH mapping theory from its original prototype to a version capable of handling real sensorimotor interaction with a real (offlce) environment. The underlying goal of this research is to demonstrate how symbolic representations and symbol-based behaviors of an autonomous robot can be grounded in non-symbolic, continuous sensorimotor interaction with a real environment through the SSH approach. The extended theory is implemented on a physical robot to explore a previously unknown environment, and to create an SSH spatial description of the environment. This dissertation describes the improved SSH mapping theory, the details of its implementation on a physical robot, and a demonstration and evaluation of several features of the implementation.

DOWNLOAD NOT AVAILABLE

AI96-258

Kay, Ph.D., Herbert. "Refining Imprecise Models and Their Behaviors". The University of Texas at Austin, Department of Computer Sciences. Report# AI96-258 (dissertation). December 1996. 143 pages.

This dissertation describes methods for simulating and refining imprecisely-defined Ordinary Differential Equation (ODE) systems. When constructing a model of a physical process, a modeler must cope with uncertainty due to incomplete knowledge of the process. For tasks such as design and diagnosis, the effects of this uncertainty must be considered. However, predicting the behavior of an imprecisely-defined model is not easy since the model covers a space of many precise instances, each of which behaves differently. While model uncertainty cannot be completely eliminated, it is possible to reduce it. Model refinement uses observations of a physical process to rule out portions of the model space that could not have produced the observations. As more experience with the physical process is gained, the imprecision in the model is further reduced. This dissertation describes three methods for reasoning with imprecise ODE models. SQsim is a simulator that produces a guaranteed bound on the behavior of an imprecise ODE model. By using a multiple-level representation and inference methods that span the qualitative-to-quantitative spectrum, SQslM produces predictions whose uncertainty is consistent with model imprecision. We demonstrate SQsim on a complex, nonlinear chemical process and compare it to other methods for simulating imprecise ODE models. MSQUID is a function estimator for fitting (and bounding) noisy data that is known to be monotonic. It uses a neural- network inspired model and nonlinear constrained optimization to search a space of monotonic functions. We prove that MSQUID can estimate any monotonic function and show that it produces better estimates than does unconstrained optimization . SQUID, which uses SQsim and MSQUID as components, is a system identification method that refines an imprecise model using a stream of observations from a physical process. SQUID uses refutation to rule out portions of the model space that are inconsistent.

DOWNLOAD NOT AVAILABLE

AI96-260

Mahoney, Ph.D., J. Jeffrey. "Combining Symbolic and Connectionist Learning Methods to Refine Certainty-Factor Rule-Bases". The University of Texas at Austin, Department of Computer Sciences. Report# AI96-260 (dissertation). May 1996. 100 pages.

This research describes the system RAPTURE, which is designed to revise rule bases expressed in certainty-factor format. Recent studies have shown that learning is facilitated when biased with domain-specific expertise and have also shown that many real-world domains require some form of probabilistic or uncertain reasoning in order to successfully represent target concepts. RAPTURE was designed to take advantage of both of these results. Beginning with a set of certainty-factor rules, along with accurately-labeled training examples RAPTURE makes use of both symbolic and connectionist learning techniques for revising the rules in order that they correctly classify all of the training examples. A modified version of backpropagation is used to adjust the certainty factors of the rules ID3's information-gain heuristic is used to add new rules and the Upstart algorithm is used to create new hidden terms in the rule base. Results on refining four real-world rule bases are presented that demonstrate the effectiveness of this combined approach. Two of these rule bases were designed to identify particular areas in strands of DNA one is for identifying infectious diseases and the fourth attempts to diagnose soybean diseases. The results of RAPTURE are compared with those of backpropagation, C4.5 KBANN and other learning systems. RAPTURE generally produces sets of rules that are more accurate than these other systems often creating smaller sets of rules and using less training time.

DOWNLOAD NOT AVAILABLE

TR-96-33

Chen, Yao-Ping. "Algorithms for VLSI Partitioning and Routing". The University of Texas at Austin, Department of Computer Sciences. Report# TR-96-33 (dissertation). November 26, 1996. 117 pages.

In this dissertation, we study several partitioning and routing problems in VLSI designs. The first one is multiple chip design partitioning. We are given a library of prefabricated chips, and we need to partition a large design into parts such that each part can be realized by a chip in the library. We present an algorithm to minimize both the number of chips and the interconnection cost in realizing a design. Next, we study a partitioning problem in Field Programmable Gate Array (FPGA) designs. We apply register relocation techniques during the clustering of registers and combinational modules to minimize the number of FPGA logic modules. This problem is exactly solved by modeling it as a linear program, following a sophisticated transformation from an integer nonlinear program. Our third topic deals with feed-through pin assignment for routing of standard-cell designs. It is a necessary process between global routing and detailed routing. We present an optimal algorithm for single row feed-through pin assignment under some reasonable constraints. It transform the original problem to a path problem on a special graph. The exact single row algorithm serves as the basic procedure in an iterative algorithm for the multiple row feed-though pin assignment. The fourth problem is clock net routing. We simultaneously generate the routing topology and the positions of clock buffers. Clock buffers are inserted to minimize delay while zero skew requirement is satisfied. Our algorithm gives excellent results on reducing wire length and phase delay, while feasible buffer positions are efficiently obtained using a graph theoretic approach. Finally, we consider partitioning clock pins into clusters aiming to minimize and balance the capacitive load of each cluster of clock pins. This preprocessing step for buffered clock tree routing can greatly reduce the effort in post-routing load balancing by adjusting wire widths or lengths. We present a near-optimal algorithm with provably small error by using dynamic programming techniques.

DOWNLOAD tr96-33.pdf

TR-96-32

Lai, Glenn G. "Efficient Searches for VLSI Applications". The University of Texas at Austin, Department of Computer Sciences. Report# TR-96-32 (dissertation). November 26, 1996. 108 pages.

Given a collection of objects, a region query finds those that intersect a specified area and a neighbor search finds the neighbors located within a specified distance of an object. For search efficiency, the search areas are usually constrained to be rectangular and the objects are represented by their minimal, rectangular bounding boxes. A spatial structure is used to store the objects for efficient searches. The focus of this dissertation is on the interactive response times as perceived by a human designer with respect to both search operations. Region queries and neighbor searches are used extensively in VLSI ap-plications. For example, to display the visible portion of a design in an edit window, search for objects that intersect the edit window. To modify an object interactively, pick the object by making the search area a point. In design-rule checking, employ the neighbor-search operation to find nearby objects that can interfere with an object. Based on properties of VLSI designs and analyses of real VLSI data, this dissertation describes the main data distributions that a spatial structure is expected to encounter, argues for a space-subdivision paradigm, presents the paradigm's worst-case performance, and explains why the worst-case performance is irrelevant in practice. Based on this paradigm, this dissertation presents HV/VH trees and hinted quad trees designed with the classical tradeoffs between memory usage and search speed, and compares them to other spatial structures.

DOWNLOAD tr96-32.pdf

TR-96-22

Kaltenbach, Markus. "Interactive Verification Exploiting Program Design Knowledge: A Model-Checker for UNITY". The University of Texas at Austin, Department of Computer Sciences. Report# TR-96-22 (dissertation). January 1997. 270 pages.

The design of concurrent programs that run reliably and efficiently on networks of interconnected computers will remain an important challenge for the foreseeable future, as the size and complexity of such systems will continue to grow. Verification techniques based on appropriate design formalism and complemented by mechanical support will play an important role for asserting the correctness and quality of these concurrent systems. In this dissertation we focus on providing suitable automated assistance to the design and verification of concurrent systems by developing a model checker or finite state programs and propositional UNITY logic. Combining the verification technique of model checking with the temporal logic of UNITY was motivated by two goals, namely to exploit the simplicity and structure of UNITY logic as to provide efficient checking algorithms for a mostly automated verification, and to allow the user to interactively supply design knowledge in order to improve the system performance. These goals have been met in three ways: (i) we have derived a model checking procedure for safety and basic progress properties that is based on the proof rules of UNITY logic, increases the efficiency of verification by making it possible to replace fixpoint computations by simple verification checks, and, moreover, takes advantage of state-based design knowledge in the form of invariants; (ii) we have developed and formally investigated a new theory of generalized progress, in which action-based hints can be provided to indicate how progress is achieved and which can be used to improve the efficiency of checking and reasoning about arbitrary progress properties; (iii) finally, we have implemented the resulting model checking procedures as part of the UNITY Verifier System and have used our implementation to demonstrate the improved verification performance with several examples.

DOWNLOAD tr96-22.pdf

TR-96-13b

Collins, Timothy Scott. "Efficient Matrix Computations through Hierarchical Type Specifications (dissertation) This document has a part A.". The University of Texas at Austin, Department of Computer Sciences. Report# TR-96-13b (dissertation). May 1996. 98 pages.

Matrix computations arise in the implementations of almost all scientific and engineering applications. Due to the physical properties of these problems and the nature of the solution methods, the resulting matrices often have complicated structure. That is, the values in the matrices have some regular pattern in their organization. Although it is well known that structure plays a crucial role in both the representational and computational efficiency of matrix computations, current programming systems offer little direct support for the representation of complicated structured matrices that arise in modern applications. Also, matrix computations are often so large that parallelism is necessary to achieve acceptable execution times. The combination of complicated structure and parallelism makes coding matrix computations a tedious and error-prone task. This dissertation investigates both the formal and pragmatic issues involved in providing powerful language and compiler capabilities for simplifying the task of constructing efficient sequential and parallel implementations for matrix computations. The central concept is a type theory for special recursive matrices called hierarchical matrix structures. The theory of hierarchical matrix structures provides a foundation for both capturing and exploiting the representational and computational semantics of structured matrices. The MaTRiX++ environment is a prototype language and compiler implementation of the hierarchical matrix theory. Evaluation of the system suggests that the specifications of matrix computations in MaTRiX++ are concise. Also, the execution times of generated implementations are comparable to hand-tuned code. Contributions of this work are both formal and practical: the theory of hierarchical matrices provides a model for describing and exploiting matrix computation semantics; the Ma-TRiX++ prototype environment supports rapid specification of complicated matrix computations without sacrificing efficiency. In addition, the hierarchical typing methodology presents a metaphor for exposing the deep relationship between physical problems and their matrix structures.

DOWNLOAD tr96-13b.pdf

TR-96-13a

Collins, Timothy Scott. "Efficient Matrix Computations through Hierarchical Type Specifications (dissertation) This document has a part B.". The University of Texas at Austin, Department of Computer Sciences. Report# TR-96-13a (dissertation). May 1996. 98 pages.

Matrix computations arise in the implementations of almost all scientific and engineering applications. Due to the physical properties of these problems and the nature of the solution methods, the resulting matrices often have complicated structure. That is, the values in the matrices have some regular pattern in their organization. Although it is well known that structure plays a crucial role in both the representational and computational efficiency of matrix computations, current programming systems offer little direct support for the representation of complicated structured matrices that arise in modern applications. Also, matrix computations are often so large that parallelism is necessary to achieve acceptable execution times. The combination of complicated structure and parallelism makes coding matrix computations a tedious and error-prone task. This dissertation investigates both the formal and pragmatic issues involved in providing powerful language and compiler capabilities for simplifying the task of constructing efficient sequential and parallel implementations for matrix computations. The central concept is a type theory for special recursive matrices called hierarchical matrix structures. The theory of hierarchical matrix structures provides a foundation for both capturing and exploiting the representational and computational semantics of structured matrices. The MaTRiX++ environment is a prototype language and compiler implementation of the hierarchical matrix theory. Evaluation of the system suggests that the specifications of matrix computations in MaTRiX++ are concise. Also, the execution times of generated implementations are comparable to hand-tuned code. Contributions of this work are both formal and practical: the theory of hierarchical matrices provides a model for describing and exploiting matrix computation semantics; the Ma-TRiX++ prototype environment supports rapid specification of complicated matrix computations without sacrificing efficiency. In addition, the hierarchical typing methodology presents a metaphor for exposing the deep relationship between physical problems and their matrix structures.

DOWNLOAD tr96-13a.pdf

TR-96-01

Stuart, Douglas Alan. "Formal Methods for Real-Time Systems". The University of Texas at Austin, Department of Computer Sciences. Report# TR-96-01 (dissertation). January 1996. 350 pages.

Computers are increasingly being used to control safety-critical systems which depend on the absolute timing of system events for their correctness. Formal specification and verification is one approach to assuring that such systems are correct. Mechanical verification can enhance the utility of formal methods by increasing their applicability and reliability. This work will focus on a particular mechanical verification technique, model checking, in the context of a specific specification language environment, RTL and Modechart. RTL is a first order logic for reasoning about the times of occurrences of system events. Modechart is a specification language introduced to organize RTL specifications. Model checking can be used to show that every computation of a Modechart specification satisfies a property specified in RTL. Computation graphs will be introduced to represent the set of all computations of a Modechart specification for model checking. Decision procedures for a number of classes of RTL formulas with respect to Modechart specifications will also be introduced. One of the disadvantages of model checking as a verification technique is that it is extremely susceptible to the state explosion problem. One focus of this work is presenting different techniques for mitigating the state explosion problem. These include substituting computation graph reachability queries for more complex RTL formulas, using monitor modes, using partial computation graphs, exploiting determinism, and using simulation-verification.

DOWNLOAD tr96-01.pdf

AI95-237

Sirosh, Joseph. "A Self-Organizing Neural Network Model Of The Primary Visual Cortex". The University of Texas at Austin, Department of Computer Sciences. Report# AI95-237 (dissertation). August 1995.

This work is aimed at modeling and analyzing the computational processes by which sensory information is learned and represented in the brain. First, a general self-organizing neural network architecture that forms efficient representations of visual inputs is presented. Two kinds of visual knowledge are stored in the cortical network: information about the principal feature dimensions of the visual world (such as line orientation and ocularity) is stored in the afferent connections, and correlations between these features in the lateral connections. During visual processing, the cortical network filters out these correlations, generating a redundancy-reduced sparse coding of the visual input. Through massively parallel computational simulations, this architecture is shown to give rise to structures similar to those in the primary visual cortex, such as (1) receptive fields, (2) topographic maps, (3) ocular dominance, orientation and size preference columns, and (4) patterned lateral connections between neurons. The same computational process is shown to account for many of the dynamic processes in the visual cortex, such as reorganization following retinal and cortical lesions, and perceptual shifts following dynamic receptive field changes. These results suggest that a single self-organizing process underlies development, plasticity and visual functions in the primary visual cortex.

DOWNLOAD UT-AI-TR-95-237.tar

AI95-239

Subramanian, Siddarth, Ph.D. "Qualitative Multiple-Fault Diagnosis of Continuous Dynamic Systems Using Behavioral Modes". The University of Texas at Austin, Department of Computer Sciences. Report# AI95-239 (dissertation). December 1995. 128 pages.

As systems like chemical plants, power plants, and automobiles get more complex, online diagnostic systems are becoming increasingly important. One of the ways to rein in the complexity of describing and reasoning about large systems such as these is to describe them using qualitative rather than quantitative models. Model-based diagnosis is a class of diagnostic techniques that use direct knowledge about how a system functions instead of expert rules detailing causes for every possible set of symptoms of a broken system. Our research builds on standard methods for model-based diagnosis and extends them to the domain of complex dynamic systems described using qualitative models. We motivate and describe our algorithm for diagnosing faults in a dynamic system given a qualitative model and a sequence of qualitative states. The main contributions in this algorithm include a method for propagating dependencies while solving a general constraint satisfaction problem, and a method for verifying the compatibility of a behavior with a model across time. The algorithm can diagnose multiple faults and uses models of faulty behavior, or behavioral modes. We then demonstrate these techniques using an implemented program called QDOCS and test it on some realistic problems. Through our experiments with a model of the reaction control system (RCS) of the space shuttle and with a level-controller for a reaction tank, we show that QDOCS demonstrates the best balance of generality, accuracy and efficiency among known systems.

DOWNLOAD NOT AVAILABLE

AI95-241

Rajagopalan, Raman M, Ph.D. "Qualitative Reasoning about Dynamic Change in the Spatial Properties of a Physical System". The University of Texas at Austin, Department of Computer Sciences. Report# AI95-241 (dissertation). December 1995. 224 pages.

Spatial reasoning is an essential part of human interaction with the physical world. Of the many models that have been developed to support automated spatial reasoning, most rely on numerical descriptions of a spatial scene. This dissertation addresses problems where only qualitative descriptions of a spatial scene are available, such as natural language understanding, qualitative design, and physics problem solving. We provide the first set of solutions, given only a qualitative description of a spatial scene, for reasoning about dynamic change in both the spatial and non-spatial properties of a physical system. We use diagrams to compactly input the spatial scene for a problem, and text to describe any non-spatial properties. To match diagram and text objects so their descriptions can be integrated, we have developed a method for describing the conceptual class of objects directly in diagrams. Then, diagram and text objects can be matched based on their conceptual class. The given problem is solved through qualitative simulation, and all spatial reasoning is done with respect to an extrinsic Cartesian coordinate system. We model the relative positions of objects through inequality constraints on the coordinates of the points of interest. Changes due to translational motion are detected by noting changes in the truth values of inequality constraints. We model the orientation of an object through knowledge of its extremal points and its qualitative angle of rotation with respect to each coordinate axis. This model has been used to reason qualitatively about the effects of rotational motion, such as changes in the area projected by one object onto another. We have implemented our spatial representation as production rules and as model fragments in the QPC qualitative modeling system. The former has been used for solving static-world problems such as understanding descriptions of an urban scene. The latter has been used to reason about situations where changes in spatial properties play a critical role, such as the operation of transformers, oscillators, generators, and motors. To support dynamic spatial reasoning, we have expanded the modeling capabilities of QPC to include methods for modeling piecewise-continuous variables, non-permanent objects, and variables with circular quantity spaces.

DOWNLOAD NOT AVAILABLE

TR-95-41

Murray, Kenneth S. "Learning as Knowledge Integration". The University of Texas at Austin, Department of Computer Sciences. Report# TR-95-41 (dissertation). November 1995. 300 pages.

A fundamental challenge for Artificial Intelligence is developing methods to build and maintain knowledge-based systems. Knowledge integration is the task of identifying how new and prior knowledge interact while incorporating new information into a knowledge base. This task is pervasive because substantial knowledge bases must be developed incrementally: segments of knowledge are added separately to a growing body of knowledge. This task is difficult because new and prior knowledge may interact in very subtle and surprising ways, and unanticipated interactions may require changes to the knowledge base. Performing knowledge integration involves determining and effecting these changes. This research investigates knowledge integration as a machine learning task. Its contributions include formalizing knowledge integration as a machine learning task, developing a computational model for performing knowledge integration, and instantiating the computational model as an implemented machine learning program. The study of knowledge integration and methods that perform it is important both for pragmatic concerns of building knowledge-based systems and for theoretical concerns of understanding learning systems. By identifying subtle conflicts and gaps in knowledge, knowledge integration facilitates building knowledge-based systems. By avoiding unnecessary restrictions on learning situations, knowledge integration reveals important sources of learning bias and permits learning behaviors that are more opportunistic than do traditional machine learning tasks. REACT is a computational model that identifies three essential activities for performing knowledge integration. Elaboration assesses how new and prior knowledge interact. The system's limited capacity to explore the interactions of new and prior knowledge requires methods to focus its attention. This focus is achieved by restricting elaboration to consider only selected segments of prior knowledge. Recognition selects the prior knowledge that is considered during elaboration. By identifying the consequences of new information for relevant prior knowledge, recognition and elaboration reveal learning opportunities, such as inconsistencies and gaps in the extended knowledge base. Adaptation exploits these learning opportunities by modifying the new or prior knowledge. KI is a machine learning program that implements the REACT model. Empirical studies demonstrate that KI provides significant assistance to knowledge engineers while integrating new information into a large knowledge base.

DOWNLOAD tr95-41.pdf

TR-95-34

Kleyn, Michiel Florian Eugene. "A High Level Language for Specifying Graph-Based Languages and their Programming Environments (dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# TR-95-34 (dissertation). November 1995. 192 pages.

This dissertation addresses the problem of creating interactive graphical programming environments for visual programming languages that are based on directed graph models of computation. Such programming environments are essential to using these languages but their complexity makes them difficult and time consuming to construct. The dissertation describes a high level specification language, Glide, for defining integrated graphical/textual programming environments for such languages. It also describes the design of a translation system, Glider, which generates an executable representation from specifications in the Glide language. Glider is a programming environment generator; it automates the task of creating the programming environments used for developing programs in graphbased visual languages. The capabilities supported by the synthesized programming environments include both program capture and animation of executing programs. The significant concepts developed for this work and embodied in the abstractions provided by the Glide language are: an approach to treating programs as structured data in a way that allows an integrated representation of graph and text structure; a means to navigate through the structure to identify program components; a query language to concisely identify collections of components in the structure so that selective views of program components can be specified; a unified means of representing changes to the structure so that editing, execution, and animation semantics associated with the language can all be captured in a uniform way; and a means to associate the graphical capabilities of user interface libraries with displaying components of the language. The data modeling approach embodied in the Glide specification language is a powerful new way of representing graph-based visual languages. The approach extends the traditional restricted mechanisms for specifying composition of text language structure. The extensions allow programming in visual languages to be expressed as a seamless extension of programming in text-based languages. A data model of a graph-based visual language specified in Glide forms the basis for specifying the program editing, language execution semantics, and program animation in a concise and abstract way.

DOWNLOAD tr95-34.pdf

TR-95-33

Wu, Shiow-Yang. "Decomposition Abstraction in Parallel Rule Languages". The University of Texas at Austin, Department of Computer Sciences. Report# TR-95-33 (dissertation). August 1995. 14 pages.

As the applications of production systems expand from traditional artificial intelligence domains into the data intensive and real-time arenas, program complexity and the volume of data also increase dramatically. Over a decade of efforts to exploit this opportunity, the previous approaches of employing parallel match and/or syntactic based multiplc-rulc-firing have failed to raise the performance to a satisfactory level. Based on the observations made in a pilot study, we found that by incorporating application semantics, it is possible to achieve a much higher level of concurrency than what can be achieved by traditional techniques. This dissertation presents a new approach called decomposition abstraction that aims at the exploration of application parallelism in production systems. Decomposition abstraction is the process of organizing and specifying parallel decomposition strategies. We propose a general object-based framework and present the formal semantics of a set of decomposition abstraction mechanisms that are applicable to any rule language. A semantic-based dependency analysis technique that uncovers hidden concurrency based on a new notion of functional dependency successfully derives parallelism that is very difficult, if not impossible, to discover by traditional syntactic analysis techniques. The effectiveness of our approach is validated both by simulation and implementation on Sequent Symmetry multiprocessor. The performance results demonstrate the potential of the decomposition abstraction approach to achieve linear and scalable speedup.

DOWNLOAD tr95-33.pdf

TR-95-17

Kartha, G. Neelakantan. "A Mathematical Investigation of Reasoning About Actions". The University of Texas at Austin, Department of Computer Sciences. Report# TR-95-17 (dissertation). May 1995. 167 pages.

Reasoning about actions is a central area of research in artificial intelligence, related to the study of commonsense and nonmonotonic reasoning, knowledge representation, planning and theorem proving. The methodology of research in this area has not been quite satisfactory; typically, a new proposal for reasoning about actions is illustrated by way of a few examples that have been known to be challenging to formalize, and then claims are made that the method works in general. This is not very satisfactory since minor modifications of the examples might prove (indeed, have proven, in many cases) to be difficult or impossible for the new proposal to handle correctly. Such an example-oriented methodology also makes it difficult to compare various formalisms and thus to synthesize new ones. In this dissertation, we present a systematic study of reasoning about actions. The shortcomings of the example-oriented methodology are avoided as follows. First, declarative languages for describing actions are introduced and their semantics defined in such a way as to capture the underlying commonsense intuitions. Different methods of reasoning about actions are presented as translations from these languages and then the adequacy of the different formalizations is established by proving the soundness and completeness of the translations. The new declarative languages we propose are capable of representing rich action domains, such as those where actions can have indirect effects. In addition, we introduce a new approach to reasoning about actions and show its adequacy in formalizing a large class of action domains. We show that, in conjunction with this approach, symbolic methods can often be employed for automating reasoning about actions. Finally, we point out some limitations of proposed methods of reasoning about actions and suggest ways to overcome these limitations.

DOWNLOAD tr95-17.pdf

AI94-219

Leow, Wee Kheng. "VISOR: Learning Visual Schemas in Neural Networks for Object Recognition and Scene Analysis". The University of Texas at Austin, Department of Computer Sciences. Report# AI94-219 (dissertation). June 1994. 166 pages.

This dissertation describes a neural network system called VISOR for object recognition and scene analysis. The research with VISOR aims at three general goals: (1) to contribute to building robust, general vision systems that can be adapted to different applications, (2) to contribute to a better understanding of the human visual system by modeling high-level perceptual phenomena, and (3) to address several fundamental problems in neural network implementation of intelligent systems, including resource-limited representation, and representing and learning structured knowledge. These goals lead to a schema-based approach to visual processing, and focus the research on the representation and learning of visual schemas in neural networks. Given an input scene, VISOR focuses attention at one component of an object at a time, and extracts the shape and position of the component. The schemas, represented in a hierarchy of maps and connections between them, cooperate and compete to determine which one best matches the input. VISOR keeps shifting attention to other parts of the scene, reusing the same schema representations to identify the objects one at a time, eventually recognizing what the scene depicts. The recognition result consists of labels for the objects and the entire scene. VISOR also learns to encode the schemas' spatial structures through unsupervised modification of connection weights, and reinforcement feedback from the environment is used to determine whether to adapt existing schemas or create new schemas to represent novel inputs. VISOR's operation is based on cooperative, competitive, and parallel bottom-up and top-down processes that seem to underlie many human perceptual phenomena. Therefore, VISOR can provide a computational account of many such phenomena, including shifting of attention, priming effect, perceptual reversal, and circular reaction, and may lead to a better understanding of how these processes are carried out in the human visual system. Compared to traditional rule-based systems, VISOR shows remarkable robustness of recognition, and is able to indicate the confidence of its analysis as the inputs differ increasingly from the schemas. With such properties, VISOR is a promising first step towards a general vision system that can be used in different applications after learning the application-specific schemas.

DOWNLOAD UT-AI-TR-94-219.tar

TR-94-33

Almstrum, Vicki Lynn. "Limitations in the Understanding of Mathematical Logic by Novice Computer Science Students". The University of Texas at Austin, Department of Computer Sciences. Report# TR-94-33 (dissertation). September 10, 2003. 183 pages.

This research explored the understanding that novice computer science students have of mathematical logic. Because concepts of logic are at the heart of many areas of computer science, it was hypothesized that a solid understanding of logic would help students grasp basic computer science concepts more quickly and would better prepare them for advanced topics such as formal verification of program correctness. This exploratory study lays the groundwork for further investigation of this hypothesis. Data for the study were the publicly available versions of the Advanced Placement Examination in Computer Science (APCS examination) and files containing anonymous individual responses of students who took these examinations. A content analysis procedure was developed to provide reliable and valid classification of multiple-choice items from the APCS examinations based on the relationship between concepts covered in each item and the concepts of logic. The concepts in the computer science subdomain of logic were clarified by means of a taxonomy developed for use in this study. Thirty-eight experts in computer science education were judges in the content analysis of the multiple-choice items. The judges' ratings provided criteria for grouping items into strongly related and not strongly related partitions. In general, the mean proportion of student respondents that correctly answered the items in a partition was lower for the strongly related than for the not strongly related partition, with a smaller standard deviation. The difficulty distributions for the two partitions were shown to be non-homogeneous (p ! .002), with the difficulty distribution for the strongly related partition skewed more towards the "very difficult" end of the distribution. The results of this study suggest that novice computer science students experience more difficulty with concepts involving mathematical logic than they do, in general, with other concepts in computer science. This indicates a need to improve the way in which novice computer science students learn the concepts of logic. In particular, pre-college preparation in mathematical logic and the content of discrete mathematics courses taken by computer science students need to be scrutinized.

DOWNLOAD tr94-33.pdf

TR-94-29

Suel, Torsten. "Routing and Sorting on Fixed Topologies". The University of Texas at Austin, Department of Computer Sciences. Report# TR-94-29 (dissertation). December 1994. 197 pages.

This thesis studies the problems of packet routing and sorting on parallel models of computation that are based on a fixed, bounded-degree topology. It establishes lower bounds for several classes of sorting networks and algorithms, and describes techniques and algorithms for packet routing and sorting on mesh-connected and related networks. A lower bound of Omega(lg n lglg n / lglglg n) is established for the depth of shuffle-unshuffle sorting networks, a class of sorting networks that maps efficiently to the hypercube and its bounded-degree variants. A stronger lower bound of Omega(lg^2 n / lglg n) is shown for a subclass of the shuffle-unshuffle sorting networks whose structure corresponds to the class of ascend and descend algorithms on the hypercube. These lower bounds also extend to restricted classes of non-oblivious sorting algorithms on hypercubic networks. A lower bound of Omega(n (lg n / lglg n)^2) is shown for the size of Shellsort sorting networks, and for the running time of non-oblivious Shellsort algorithms. The lower bound establishes a trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence. For the problems of permutation routing and sorting on meshes and related networks, a set of techniques is proposed that can be used to convert many randomized algorithms into deterministic algorithms with matching running time and queue size. Applications of these techniques lead to a deterministic algorithm for sorting on the two-dimensional mesh that achieves a running time of 2n+o(n), and a fairly simple deterministic algorithm for routing with a running time of 2n+o(n) and very small queue size. Some other applications of the techniques are also described. Finally, the thesis gives algorithms and lower bounds for routing and sorting on multi-dimensional meshes and meshes with bus connections.

DOWNLOAD tr94-29.pdf

AI93-194

Lee, Wood Wai. "A Qualitative Simulation Based Method To Construct Phase Portraits". The University of Texas at Austin, Department of Computer Sciences. Report# AI93-194 (dissertation). January 1993. 235 pages.

Shortcomings of qualitative simulation, and of quantitative simulation, motivate combining them to do simulations exhibiting strengths of each. The resulting class of techniques is termed qualitative-quantitative simulation . Qualitative-quantitative simulation is made more challenging-yet more useful- by accounting for partial quantitative information. Available quantitative information is often incomplete, so allowing numerical values to be qualified with error terms or tolerances expressed as intervals is important. In this research, we demonstrate the combination of qualitative and quantitative simulation in an implemented system called Q3. Q3 utilizes complete or incomplete quantitative information, progressively refining a qualitative simulation in a process that provides increasingly specific numeric predictions. The step size refinement algorithm is central to Q3. Step size refinement is discussed with respect to three properties often used in analyzing simulation algorithms: correctness of the inferences, theoretical convergence to the true solution, and stability of solutions when the model parameters and initial conditions are incompletely specified. Q3 has been successfully applied to model based prediction, measurement interpretation diagnosis, and finding probabilities of qualitative behaviors.

DOWNLOAD NOT AVAILABLE

AI93-201

Franke, David Wayne. "A Theory of Teleology". The University of Texas at Austin, Department of Computer Sciences. Report# AI93-201 (dissertation). May 1993. 188 pages.

A representation language for teleological descriptions, or descriptions of purpose, is defined. The teleological language, TeD, expresses the descriptions of purpose in terms of design modifications that guarantee the satisfaction of design specifications. These specifications express potential behaviors the designed artifact should or should not exhibit. We define an abstraction relation on behavior and implement model checking and classification algorithms that compute this abstraction relation. The model checking algorithm determines whether or not a behavior satisfies a specification. The classification algorithm provides effective indexing of behaviors and teleological descriptions. We implement an acquisition technique for teleological descriptions and demonstrate how teleological descriptions can subsequently be used in diagnosis, explanation, case-based reasoning, design by analogy, and design reuse. We demonstrate the behavior language, teleology language, acquisition of teleological descriptions, and application of teleological descriptions in explanation, diagnosis, and design reuse via examples in the thermal, hydraulic, electrical, and mechanical domains. We define additional teleological operators that express purposes like prevent, order, synchronize, maintain, and regulate, demonstrating the ability to represent common human-generated descriptions of purpose in TeD. Expressing the purpose of preventing an undesirable behavior is unique to TeD, and is an example of TeD's ability to express purposes regarding missing behaviors and components removed from a design. The teleology language developed in this work represents a significant advance over previous work by providing a formal language that 1) is independent of any particular domain of mechanisms or behavior language, 2) can be effectively acquired during the design process, and 3) provides an effective means of classifying and indexing teleological descriptions.

DOWNLOAD NOT AVAILABLE

AI93-205

Lee, Xiang-Seng. "Temporal and Spatial Analysis in Knowledge-based Physics Problem Solving". The University of Texas at Austin, Department of Computer Sciences. Report# AI93-205 (dissertation). December 1992. 266 pages.

Physics problems as stated in textbooks are typically informal and incomplete, and not amenable to the direct application of the general laws of physics. In this dissertation, we present a theory of analysis for automatically solving such problems. In particular, the theory provides a detailed methodology for constructing a formal problem representation, called physical representation, upon which physics laws may be appropriately selected and instantiated. With the equations generated by these laws, the solutions to these problems are obtained through strictly mathematical manipulations. This theory provides a well-structured domain language, in which it is relatively easy to state mechanical knowledge and mechanics problems. In the language we introduce the notion of basic physical phenomenon for representing the knowledge of physical situations and events. This notion serves as both the building block for the physical representation and as a vehicle for accessing the appropriate physical laws. Both basic physical phenomena and more traditional temporal entities, instants and intervals, may be used as time references. This dual-system representation facilitates bi-level abstractions of time necessary to avoid discontinuities introduced by short impulsive phenomena, e.g., collisions, and corresponds well with human-like temporal reasoning. The language also includes an ontology of space, using multiple abstractions to account for its inherent complexity, and representation schemes for physical laws and equations. The other key ingredient of the theory is a repertoire of ordered knowledge sources, formulated to specify the derivation procedures of a physical representation. The domain language, in which these knowledge sources are written, has a structure which is useful as a theoretical basis for determining their ordering and inference step sizes. This practice has proven crucial for building knowledge-based systems that are easy to debug and modify. The theory has been implemented and tested in a computer program which has successfully solved several relatively difficult problems selected from a widely used textbook. Novel methods implemented in the program for intelligently selecting appropriate physics laws and for solving equations are also discussed.

DOWNLOAD Available from University Microfilms

AI93-207

Farquhar, Adam. "Automated Modeling of Physical Systems in the Presence of Incomplete Knowledge". The University of Texas at Austin, Department of Computer Sciences. Report# AI93-207 (dissertation). September 1993. 149 pages.

This dissertation presents an approach to automated reasoning about physical systems in the presence of incomplete knowledge which supports formal analysis, proof of guarantees, has been fully implemented, and applied to substantial domain modeling problems. Predicting and reasoning about the behavior of physical systems is a difficult and important task that is essential to everyday common sense reasoning and to complex engineering tasks such as design, monitoring, control, or diagnosis. A capability for automated modeling and simulation requires - expressiveness to represent incomplete knowledge - algorithms to draw useful inferences about non-trivial systems, and - precise semantics to support meaningful guarantees of correctness In order to clarify the structure of the knowledge required for reasoning about the behavior of physical systems, we distinguish between the model building task which builds a model to describe the system, and the simulation task which uses the model to generate a description of the possible behaviors of the system. This dissertation describes QPC, an implemented approach to reasoning about physical systems that builds on the expressiveness of Qualitative Process Theory [Forbus,1986] and the mathematical rigor of the QSIM qualitative simulation algorithm [Kuipers,1986]. The semantics of QPC's modeling language are grounded in the mathematics of ordinary differential equations and their solutions. This formalization enables the statement and proof of QPC's correctness. If the domain theory is adequate and the initial description of the system is correct, then the actual behavior of the system must be in the set of possible behaviors QPC predicts. QPC has been successfully applied to problems in Botany and complex examples drawn from Chemical Engineering, as well as numerous smaller problems. Experience has shown that the modeling language is expressive enough to describe complex domains and that the inference mechanism is powerful enough to predict the behavior of substantial systems.

DOWNLOAD NOT AVAILABLE

TR-93-20

Bayerdorffer, Bryan Carl. "Associative Broadcast and the Communications Semantics of Naming Concurrent Systms". University of Texas at Austin, Department of Computer Sciences. Report# TR-93-20 (dissertation). November 1993. 207 pages.

Much of the complexity of concurrent program design lies in the specification of patterns of communication: flows of information among objects (e.g. processes) expressed as functions of the global computation state. Underlying the communication mechanisms of every concurrent system is a naming system, whic is used to specify the objects participating in each communication. We call those characteristics of naming systems that determine the patterns of communication that can be specified the communication semantics of naming systems. A more expressive naming system allows communication to be specified at a higher level of abstraction. The available communication abstractions are significant in the choice of an algorithm, in which specific patterns of communication are manifest, to solve a particular problem. Thus the choice or design of a naming system often significantly affects the design of concurrent programs. Yet naming systems have not been widely studied as independent components of concurrent systems. This has led to empirical design and inappropriate choices of naming systems, which hinder the specification of complex patterns of communication and constrain algorithm design, yielding awkward programs and inefficient executions. To simplify the use of naming systems in specifying communication, and to make more precise our understanding of their communication semantics, we adopt a two fold approach: The development of a formal taxonomy of naming systems, and the design of a specific naming system and communication primitive, called Associative Broadcast, that enable straightforward specification of complex communication patterns. The taxonomy defines a set of orthogonal properties that characterize the ability ofnaming systems to express fundamental patterns of communication. Naming systems are classified and ranked in a partially ordered hierarchy according to their properties. The hierarchy allows systematic comparison of naming systems, and selection of naming systems for the solution of problems requiring specific properties. Associative Broadcast resides at the top of the hierarchy, and allows the specification of a dynamic, descriptively named target set of objects as the destination of a message by defining names to be propositional expressions over sets of object attributes, and by using delayed resolution. We apply Associative Broadcast to obtain algorithms with desirable symmetry, robustness, concurrency, and efficiency properties for problems in the areas of distributed constraint reduction, database consistency in the presence of network partition failures, and virtual time synchronization.

DOWNLOAD tr93-20.pdf

TR-93-19

Bunda, John D. "Instruction Processing Optimization Techniques for VLSI Microprocessors (dissertation)". University of Texas at Austin, Department of Computer Sciences. Report# TR-93-19 (dissertation). November 1993. 174 pages.

The RISC minimalist paradigm of computer architecture has inspired machines that are straightforward to understand and implement. There has been disagreement as to the precise definition of RISC, and strong results about the relative value of RISC over other architectural approaches are evasive. For the purposes of this thesis, a RISC architecture consists of a general-purpose register file and a simple multi-stage pipeline for executing single instructions at a peak rate of one per clock cycle. Even within the parameters of a RISC processor architecture, there remain design decisions that can significantly impact cost and processing performance. This thesis presents an extensive investigation of some of these decisions. A common criticism of RISC machines is low code density; programs for RISC architectures tend to contain more instructions and occupy more physical storage than those for machines with more complex and powerful instruction sets. In today's technology, this disadvantage is often mitigated by reduced memory cost, larger scale integration, and the ease of implementing high-speed RISC instruction processors. It is unclear, however, how evolution in technology and processor applications influences this tradeoff; it is prudent to continue examining consequences of popular RISC design choices with respect to these changing parameters. For example, microprocessor clock cycle times are decreasing at a faster rate than memory access times and interconnect speed. Moreover, as speed and device densities increase, so does the problem of managing and removal of heat energy from processor chips. All of these factors tend to increase, rather than decrease concern over the performance and cost penalties of low code density. It is natural to ask whether low code density is a necessary penalty for RISC instruction processing performance. Within the framework of a parameterized design for a RISC instruction processor, this thesis presents analysis of these processing performance and energy-efficiency issues through software simulation.

DOWNLOAD tr93-19.pdf

TR-93-09

Yu, Yuan. "Automated Proofs of Object Code For a Widely Used Microprocessor". University of Texas at Austin, Department of Computer Sciences. Report# TR-93-09 (dissertation). 734 pages.

Computing devices can be specified and studied mathematically. Formal specification of computing devices has many advantages -- it provides a precise characterization of the computational model and allows for mathematical reasoning about models of the computing devices and programs executed on them. While there has been a large body of research on program proving, work has almost exclusively focused on programs written in high level programming languages. This thesis addresses the very important but largely ignored problem of machine code program proving. In this thesis we have formally described a substantial subset of the MC68020, a widely used microprocessor built by Motorola, within the mathematical logic of the automated reasoning system Nqthm, a.k.a. the Boyer-Moore Theorem Proving System. Based on this formal model, we have mechanized a mathematical theory to facilitate automated reasoning about object code programs. We then have mechanically checked the correctness of MC68020 object code programs for binary search, Hoare's Quick Sort, the Berkeley Unix C string library, and other well-known algorithms. The object code for these examples was generated using the Gnu C, the Verdix Ada, and the AKCL Common Lisp compilers.

DOWNLOAD tr93-09.pdf

TR-93-03

Jain, Ravi. "Scheduling Data Transfers in Parallel Computers and Communications Systems". University of Texas at Austin, Department of Computer Sciences. Report# TR-93-03 (dissertation). February 1993. 225 pages.

The performance of many applications of parallel computers and communications systems is limited by the speed of data transfers rather than the speed of processing. An important, but neglected, aspect of resource management to overcome this bottleneck is the scheduling of data transfers. Data transfer scheduling differs from traditional scheduling problems in that data transfer tasks require multiple resources simultaneously, rather than a single resource serially, in order to execute. We study the data transfer scheduling problem by first defining a general model for precisely specifying and classifying scheduling problems. We use the model for the recognition of the similarity of seemingly different problems from different application areas, for the systematic transformation of one problem specification into that of a seemingly different problem, and for the systematic decomposition of a problem specification into solvable subproblems. We obtain polynomial-time, optimal and approximate algorithms for a wide range of data transfer scheduling problems under a variety of architectural and logical constraints, including communication architectures in which resources are fully connected, communication architectures with a tree topology, and the presence of mutual exclusion and precedence constraints. Our algorithms either generalize previous results for these problems, or provide better performance, or both. Our results are applicable to both parallel computers and communications systems, including certain types of shared-bus multiprocessor systems such as the Sequent and the IBM RP3, hierarchical switching systems, tree-structured multiprocessor architectures, and intersatellite communications systems.

DOWNLOAD tr93-03.pdf

AI92-177

Ng, Hwee Tou. "A General Abductive System with Application to Plan Recognition and Diagnosis". The University of Texas at Austin, Department of Computer Sciences. Report# AI92-177 (dissertation). June 1992. 145 pages.

A diverse set of intelligent activities, including natural language understanding, diagnosis, and scientific theory formation, requires the ability to construct explanations for observed phenomena. In this thesis, we view explanation as abduction, where an abduction explanation is a consistent set of assumptions which, together with background knowledge, logically entails a set of observations.

DOWNLOAD NOT AVAILABLE

AI92-181

Richards, Bradley Lance. "An Operator-Based Approach to First-Order Theory Revision". The University of Texas at Austin, Department of Computer Sciences. Report# AI92-181 (dissertation). August 1992. 178 pages.

This thesis presents a system, FORTE (First-Order Revision of Theories from Examples), that performs theory revision in first-order domains. Moving to a first-order representation creates many new challenges, such as argument selection and recursion. but it also opens many new application areas, such as logic programming and qualitative modelling, that are beyond the reach of propositional systems. FORTE uses a hill-climbing approach to revise theories. It identifies possible errors in the theory and calls on a library of operators to develop possible revisions. The best revision is implemented, and the process repeats until no further revisions are possible. Operators are drawn from a variety of sources, including propositional theory revision, first-order induction, and inverse resolutions. FORTE has been tested in a wide variety of domains. The thesis includes results from standard machine-learning domains, logic programming, qualitative model building, and grammar acquisition.

DOWNLOAD NOT AVAILABLE

AI92-183

Acker, Liane. "Access Methods for Large, Multifunctional Knowledge Bases". The University of Texas at Austin, Department of Computer Sciences. Report# AI92-183 (dissertation). August 1992. 147 pages.

The goal of this research is to develop methods for representing and accessing knowledge to support multiple tasks. The goals of the research are threefold. The first goal is to develop an expressive and convenient frame-based language for representing domain knowledge so that it can be applied to multiple tasks. A single comprehensive, fine grained representation of domain knowledge that can support a variety of applications is more flexible and cost-effective than several special purpose knowledge bases. The second goal of the research is to make users of a knowledge base less dependent on the particulars of how knowledge is represented. This is achieved by providing a content addressable knowledge base and by providing access to concepts in the virtual knowledge base. Users can access frames in the knowledge base by description as well as by name, regardless of whether they exist explicitly or implicitly in the knowledge base. The third goal of the research is to develop computational methods for accessing from a knowledge base coherent portions of knowledge about a given concept (called viewpoints of concepts). Viewpoints are essential for a variety of tasks, including explanation generation, compositional modeling, problem solving, and machine learning. This research identifies several types of viewpoints and develops methods for constructing viewpoints of each type. Evaluation suggests that the viewpoints generated by these methods are comparable in coherence to human- generated viewpoints.

DOWNLOAD NOT AVAILABLE

TR-92-44

Turpin, Russell. "Programming Data Structures in Logic". University of Texas at Austin, Department of Computer Sciences. Report# TR-92-44 (dissertation). December 1992. 170 pages.

Current programming languages that are grounded in a formal logic -- such as pure Lisp (based on the lambda calculus) and Prolog (based on Horn clause logic) -- do not support the use of complex, pointer-based data structures. The lack of this important feature in logically grounded languages contrasts sharply with its strong support in the imperative programming languages that have enjoyed wide application, of which C is a prime example. Unfortunately, the formal methods for reasoning about imperative languages have not proved broadly useful for reasoning about programs that manipulate complex, pointer-based data structures. Between these two camps resides an open question: How can we verify programs involving complex, pointer-based data structures? This work gives an answer to this question. It describes a programming language in which a programmer can define logical predicates on data structures and pointers, and use these predicates to specify programs that manipulate complex, pointer-based data structures. These programs may dynamically allocate memory and destructively modify their arguments. This solution is grounded in two theoretical advances. (1) This work develops a first-order logic for data structures that formalizes the notions that are necessary for defining and reasoning about relationships between data structures, including notions such as the address of a data structure, pointer reference, reachability via pointer reference, and data structure overlap. (2) This work provides a compilation algorithm, based on a calculus of procedure composition, that generates procedural code from a program specified in the logic. Compilation is in the style of automatic programming, and relies on the programmer, using theorem proving tools, to verify assertions in the logic that are generated by the compilation algorithm.

DOWNLOAD tr92-44.pdf

TR-92-42

Kuo, Chin-Ming. "Parallel Execution of Production Systems". University of Texas at Austin, Department of Computer Sciences. Report# TR-92-42 (dissertation). November 1992. 152 pages.

The production system or rule-based system paradigm is a widely used form of building expert systems or artificial intelligence applications involving knowledge representation and knowledge base search. As the complexity and size of expert system applications expand, parallelizing production systems becomes an attractive approach in attempts to speedup the executions. Previous attempts at parallel structuring of rule-based programs have failed to achieve desired levels of parallelism. This research is a comprehensive approach to the parallelization of rule-based programs. The structure of the productions systems is examined and static analysis techniques are developed. Several sources of run-time parallelism are developed to restructure the cases where the dynamic behaviors of the systems can not be detected by the compile-time analysis. We propose a new production system language (CREL), suitable for parallel implementation, to allow asynchronous execution.

DOWNLOAD tr92-42.pdf

TR-92-34

Staskauskas, Mark G. "Specification and Verification of Large-Scale Reactive Programs". University of Texas at Austin, Department of Computer Sciences. Report# TR-92-34 (dissertation). August 1992. 192 pages.

The UNITY methodology has attracted wide attention because of its elegant logic for specifying and reasoning about concurrent programs. However, the UNITY examples tackled so far are much smaller in scale than the problems typically encountered in practice. The goal of this dissertation is the identification of extensions to UNITY that will enable it to be applied to significantly larger problems. To explore possible extensions, we have applied UNITY to three large-scale examples drawn from industrial applications: the I/O subsystem portion of the GCOS operating system; a distributed electronic funds-transfer system; and a telephone-switching system.

DOWNLOAD tr92-34.pdf

AI91-156

Hayashi, Akira. "Geometrical Motion Planning for Highly Redundant Manipulators Using a Continuous Model". The University of Texas at Austin, Department of Computer Sciences. Report# AI91-156 (dissertation). March 1991. 156 pages.

There is a need for highly redundant manipulators to work in complex, cluttered environments. Our goal is to plan paths for such manipulators efficiently. The path planning problem has been shown to be PSPACE-complete in terms of the number of degrees of freedom (DOF) of the manipulator. We present a method which overcomes the complexity with a strong heuristic: utilizing redundancy by means of a continuous manipulator model. The continuous model allows us to change the complexity of the problem from a function of both the DOF of the manipulator (believed to be exponential) and the complexity of the environment (polynomial), to a polynomial function of the complexity of the environment only. The power of the continuous model comes from the ability to decompose the manipulator into segments, with the number, size, and boundaries of the segments, varying smoothly and dynamically. First, we develop motion schemas for the individual segments to achieve a basic set of goals in open and cluttered space. Second, we plan a smooth trajectory through free space for a point robot with a maximum curvature constraint. Third, the path generates a set of position subgoals for the continuous manipulator which are achieved by the basic motion schemas. Fourth, the mapping from the continuous model to an available jointed arm provides the curvature bound and obstacle envelopes required (in step 2) to guarantee a collision-free path. The validity of the continuous model approach is also supported by an extensive simulation which we performed. While the simulation has been performed in 2-D, we show a natural extension to 3-D for each technique we have implemented for the 2-D simulation.

DOWNLOAD NOT AVAILABLE

AI-91-161

Hartman, John. "Automatic Control Understanding for Natural Programs". The University of Texas at Austin, Department of Computer Sciences. Report# AI-91-161 (dissertation). May 1991. 227 pages.

Program understanding involves recognizing abstract concepts like "read-process loop" in existing programs. Programmers spend much of their time understanding programs, so studying and automating the process has many benefits. Programming plans are units of programming knowledge connecting abstract concepts and their implementations. Existing research assumes that plan instances can be recognized to recover the programmer's abstract concepts and intentions, but this approach has not been confirmed empirically. We present a practical method for bottom-up control concept recognition in large, unstructured imperative programs. Control concepts are abstract notions about interactions between control flow, data flow and computation, such as "do loop", "read process loop", and "bounded linear search". They are recognized by comparing an abstract program representation against a library of standard implementation plans. The program representation is a hierarchical control flow/data flow graph decomposed into a tree of sub-models using propers (single entry/exit control flow sub-graphs). Plans are represented by similar graphs with added qualifications. Recognition is based on simple matching between sub-models and plans. The method was implemented in the UNPROG program understander and tested with Cobol and Lisp source programs. This method is robust, efficient, and scalable. The program representation can be formed for all language constructs which permit static determination of control and data flow. Comparing sub- models and comparisons increases linearly with program size. UNPROG has been applied to automatic Cobol restructuring. Knowledge associated with plans and concepts permits more specific and insightful transformation, code generation, and documentation than is possible with syntactic methods. Control understanding can similarly raise the level of other reverse engineering and re-engineering tools for applications like analysis, documentation, and translation. We also showed how our method and UNPROG can be used for empirical study of programs at the conceptual level. Results can be used to improve recognizer performance, acquire plans, catalog natural plans and concepts, test the hypothesis that programs are planful, and characterize program populations.

DOWNLOAD NOT AVAILABLE

AI91-162

Throop, David Rutherford. "Model-Based Diagnosis of Complex, Continuous Mechanisms". The University of Texas at Austin, Department of Computer Sciences. Report# AI91-162 (dissertation). August 1991. 135 pages.

In diagnosis, when a hypothesis proposes a variable's value, several different lines of evidence may be considered; the different evidence must be arbitrated. The result of this arbitration consists of a single best estimate of the variable value and of a measure of that estimate's plausibility. The plausibility measure reflects the degree of agreement among the lines of evidence. This report describes HEATX, a program for model-based diagnosis of non-linear mechanisms with continuous variables. Previous work in model-based diagnosis has avoided arbitrating numeric evidence, often by representing continuous variables as discrete symbols (e.g., high, cold). Such restricted representation have had difficulty in diagnosing mechanisms with feedback or reconvergent fanout. HEATX represents numerical data explicitly in the hypotheses and in the inferencing procedures; it is thereby able to arbitrate evidence numerically. HEATX uses both nonlinear numerical simulations and approximate linear models to perform diagnosis in the domain of heat-exchanger networks. The response of these networks to changes in their inputs is nonlinear; the networks also have feedback and reconvergent fanout. This dissertation introduces several novel techniques for diagnosing such networks. It interleaves the generation of complete fault hypotheses with several tests on partially formed hypotheses. Two of these tests are the qualitative filter and the clustering filter. The qualitative filter analyzes the signs of gains between fault and symptom variables. The clustering filter constructs linear approximations to individual components and assembles these into a linear model of the network. It then uses the linear model to assess the consistency of a hypothesis. It does so by determining whether there is a value for the candidate fault variable which is consistent with the quantitative values of the symptom variables; the degree of agreement between the symptoms and best value for the fault variable is used to score the hypothesis. This filter is extended to multi-fault diagnosis, in which values for several fault variable may be estimated and judged simultaneously.

DOWNLOAD UT-AI-TR-91-162.pdf

AI91-163

Berleant, Jared Daniel. "The Use of Partial Quantitative Information with Qualitative Reasoning". The University of Texas at Austin, Department of Computer Sciences. Report# AI91-163 (dissertation). August 1991. 131 pages.

There is a need for combining qualitative and quantitative simulations, to do simulation tasks that would be difficult using either alone. This task is made more difficult by the fact that available quantitative information may be incomplete, bounding values with intervals or describing them with probability distribution functions. This research demonstrates the combination of qualitative and quantitative simulation in an implemented system, Q3. Q3 utilizes partial or complete quantitative information, to gradually refine a qualitative simulation into a simulation that has properties and advantages of both qualitative simulations and quantitative ones. The technique exemplified by Q3 is shown to possess properties often used in analyzing both qualitative and quantitative simulators. Qualitative and quantitative inferences are correct. Theoretical convergence to the true solution and stability in the presence of partial model inputs are also shown. Q3 has been applied to the problem of finding probabilities of qualitative behaviors, an important problem. Partial quantitative characterization of model inputs, in the form of intervals and probability distributions, may be used to bound the probabilities of different behaviors. This is demonstrated for simple models including one in the dependability analysis application domain.

DOWNLOAD NOT AVAILABLE

AI91-164

Ourston, Dirk. "Using Explanation-Based and Empirical Methods in Theory Revision". The University of Texas at Austin, Department of Computer Sciences. Report# AI91-164 (dissertation). August 1991. 125 pages.

The knowledge acquisition problem is a continuing problem in expert system development. The knowledge base (domain theory) initially formulated by the expert is usually only an approximation to the correct theory for the application domain. This initial knowledge base must be refined (usually manually) as problems are discovered. This research addresses the knowledge base refinement problem for classification tasks. The research provides an automatic method for correcting a domain theory in the light of incorrect performance on a set of training examples. The method uses attempted explanations to focus the correction on the failing part of the knowledge base. It then uses induction to supply a correction to the knowledge base that will render it consistent with the training examples. Using this technique, it is possible to correct overly general and overly specific theories, theories with multiple faults at various levels in the theory hierarchy, and theories involving multiple concepts. Methods have been developed for making corrections even in the presence of noisy data. Theoretical justification for the method is given in the form of convergence results that predict that the method will eventually converge to a hypothesis that is within a small error of the correct hypothesis, given sufficient examples. Because the technique currently relies on theorem proving for much of the analysis, it is quite expensive to computationally and heuristic methods for reducing the computational burden have been implemented. The system developed as part of the research is called EITHER (Explanation-based Inductive THeory Extension and Revision). EITHER uses propositional Horn clause logic as its knowledge representation, with examples expressed as attribute-value lists. The system has been tested in a variety of domains including revising a theory for the identification of promoters in DNA sequences and a theory for soybean disease diagnosis, where it has been shown to outperform a purely inductive approach.

DOWNLOAD NOT AVAILABLE

TR-91-39

Campbell III, A. T. "Modeling Global Diffuse Illumination for Image Synthesis". University of Texas at Austin, Department of Computer Sciences. Report# TR-91-39 (dissertation). December 1991. 155 pages.

Rapid developments in the design of algorithms for rendering globally illuminated scenes have taken place in the past five years. Net energy methods such as radiosity algorithms have become effective at computing the energy balance for scenes containing diffusely reflecting objects. Such methods first break up a scene description into a large set of elements, or possibly several levels of elements. Energy transfers among these elements are then determined using a variety of means. While much progress has been made in the design of energy transfer algorithms, little or no attention has been paid to the proper generation of the mesh of surface elements. This dissertation presents a technique for adaptively creating a mesh of surface elements as the energy transfers are computed. The method allows large numbers of small elements to be placed at parts of the scene where the most active energy transfers occur without requiring that other parts of the scene be subdivided needlessly to the same degree. As a result, the computational effort in the energy transfer computations can be concentrated where it has the most effect. Since the sources of direct and indirect illumination in the scene are polygonal elements, the effects of light sources with finite area must be computed. Most methods simplify the problem by approximating the area source with a collection of point sources. We present an object space algorithm to model illumination from polygonal light sources analytically. The result is a collection of smooth-shaded polygonal facets that may be rendered from any viewing position. Binary Space Partitioning trees are used to compute umbra and penumbra boundaries efficiently. Fast analytic techniques are developed for illumination calculations. Numerical optimization methods ensure that the shading function is sampled finely enough to find all significant illumination gradations. Illumination calculations are optimized to concentrate computational effort on parts of the scene where they are most needed.

DOWNLOAD tr91-39.pdf tr91-39.pdf

TR-91-34

Aahlad, Yeturu. "Balanced Sequencing Protocols". University of Texas at Austin, Department of Computer Sciences. Report# TR-91-34 (dissertation). November 1991. 122 pages.

The protocol used to control the sequence of execution of events of a distributed computation has a significant impact on its performance. Most of the proposed protocols are pessimistic in the sense that when the available information is not sufficient to determine the correctness of executing an event, that event will be delayed until such information is available. Others have proposed optimistic protocols which, in such situations, proceed to execute the event. When the necessary information becomes available, if it turns out that the event should not have been executed, the protocol takes appropriate action to recover from the mistake. This research addresses ways to strike an appropriate balance between the extremes of optimism and pessimism in a sequencing protocol and evaluates the benefits of doing so. The term Balanced Sequencing Protocol refers to protocols whose degree of optimism can be varied across a spectrum of possibilities ranging from optimistic to pessimistic by tuning one or more parameters of the protocol. Two approaches are employed in the investigation: (1) a general protocol for sequencing any program at any specified level of optimism, and (2) balanced sequencing protocols specialized for some common distributed computing primitives and paradigms, namely, producer-consumer, distributed semaphores and distributed locking. For these specialized protocols, the range of circumstances where balanced protocols do better than both extremes and the optimal balance are analytically determined. A model of distributed databases used in a previously published simulation experiment is studied, and balanced locking is demonstrated to perform better than conventional locking when recovery cost is less than 20 message delays. During the course of this research, a previously unknown phenomenon which can cause the performance of optimistic protocols to degrade over time was identified, and its effects were quantified for a simple system. A solution to this problem based on balanced sequencing is proposed.

DOWNLOAD tr91-34.pdf

TR-91-29

Levy, Eliezer. "Semantics-Based Recovery in Transaction Management Systems". University of Texas at Austin, Department of Computer Sciences. Report# TR-91-29 (dissertation). August 1991. 89 pages.

A cornerstone of the transaction paradigm is the notion of atomicity. The principle that forms the basis for obtaining transaction atomicity in most contemporary database systems is to prohibit transactions from accessing uncommitted data. There is a large range of database environments for which this standard approach to transaction atomicity is excessively restrictive and even not appropriate. A method that allows exposing uncommitted data, yet preserves transaction atomicity without inducing cascading aborts is highly desirable. Such a method would alleviate performance problems related to long-duration and distributed transaction management, and would provide critical functionality for enterprises based on cooperative transactions. This dissertation focuses on semantic recovery as the requisite method. Semantic undoing, referred to as compensation, is carried out by a compensating transaction which is associated with a specific forward transaction. A compensating transaction faces the intricate task of undoing its forward transaction while obliterating the effects of other transactions to a minimal extent and preserving data consistency. Only with the aid of the specific semantics of the application at hand can this task be accomplished. Compensation, and semantic recovery in general, can be utilized in the realm of distributed transaction management systems. Supporting atomicity of multi-site transactions in a distributed system is equated with long-duration delays, blocking, and loss of the local autonomy of the individual sites. The two-phase commit protocol embodies these deficiencies. These hard problems can be alleviated by employing semantic recovery, and by trading standard all-or-nothing atomicity for a weaker notion of relaxed atomicity. Facing the relevant impossibility results in distributed computing, this new direction is well justified. Relaxed atomicity is characterized by an asynchronous process of recovery from decentralized and uncoordinated local decisions as to whether to commit or abort a multi-site transaction. This recovery process finally leads to a unanimous outcome. Relaxing standard atomicity interacts in a subtle way with correctness and concurrency control issues. Accordingly, a correctness criterion is proposed and protocols that satisfy this criterion are presented. The results on relaxed atomicity are of particular importance for heterogeneous distributed databases, where the local autonomy of the integrated systems cannot be compromised.

DOWNLOAD tr91-29.pdf tr91-29.pdf

TR-91-14

Cheng, Albert Mo Kim. "Analysis and Synthesis of Real-Time Rule-Based Decision Systems". University of Texas at Austin, Department of Computer Sciences. Report# TR-91-14 (dissertation). April 1991. 284 pages.

Real-time decision systems (RTDS's) are computer-controlled systems that must react to events in the external environment by performing decision-intensive computation sufficiently fast to meet specified timing and safety constraints. This dissertation investigates a class of these systems where decisions are computed by an equational rule-based program. Two fundamental problems are identified: (1) the analysis of rule-based RTDS's in order to verify that the specified timing and safety properties are satisfied prior to their execution, and (2) the synthesis of rule-based RTDS's that are guaranteed to meet the specified timing constraints in addition to the safety constraints. Two complementary approaches have been developed to solve the first problem: (1) model checking of the global state transition graph representing the program, and (2) static analysis of the program. These approaches are combined to form the cornerstone of the General Iterative Analysis Algorithm. The applicability of this analysis technique is further enhanced by the development of a facility with which the rule-based programmer can specify domain-specific knowledge in the language Estella in order to validate the performance of an even wider range of programs. Two approaches also have been identified to tackle the second problem: (1) transforming the given equational rule-based program by adding, deleting, and/or modifying rules, and (2) optimizing the scheduler to select the rules to fire such that the variables in the program will always converge to stable values within the response time constraint. The complexity and size of real-time decision systems often necessitates the use of computer-aided design tools. This dissertation describes a suite of analysis tools based on our theoretical framework which have been implemented to ensure that equational rule-based programs written in the language EQL can indeed meet their specified timing constraints.

DOWNLOAD tr91-14.pdf

TR-91-02

Haruyama, Nick Shinichiro. "New Routing Strategies for VLSI". University of Texas at Austin, Department of Computer Sciences. Report# TR-91-02 (dissertation). December 1990. 158 pages.

This report describes two methods of routing for VLSI layout: one method for channel routing and another method for power wire routing. Our two-layer channel router is designed to find solutions which minimize both wiring area and number of vias simultaneously. Our method, called topological channel routing, analyzes the topological relationship of wires before the wires are mapped onto the channel. A unique layout design rule called an interleaving mesh is used. The interleaving mesh prohibits long wires on one layer from overlapping with wires on the other layer, thus has smaller cross talks of signals because of smaller capacitive couplings between those wires on different layers. Experimental results show that the algorithm generates very good solutions. For example, we have obtained a height of 41 for the famous Deutsch's Difficult Example without any parallel overlaps of wires and simultaneously a via count of 186, which is one of the best results ever reported in the literature. Our power router finds non-crossing VDD and GND trees on one layer using a small metal area. The solution is obtained under the constraints of metal migration and voltage drop. Experimental results show that the power wire area is considerably smaller than a previously developed method for single-layer routing.

DOWNLOAD tr91-02.pdf

AI90-121

Byun, Yung-Tai. "Spatial Learning Mobile Robots with a Spatial Semantic Hierarchical Model". The University of Texas at Austin, Department of Computer Sciences. Report# AI90-121 (dissertation). January 1990. 235 pages.

The goal of this dissertation is to develop a spatial exploration and map-learning strategy for a mobile robot to use in unknown, large-scale environments. Traditional approaches aim at building purely metrically accurate maps. Because of sensorimotor errors, it is hard to construct accurately such maps. However, in spite of sensory and computation limitation, humans explore environments, build cognitive maps from exploration, and successfully path-plan, navigate, and place-find. Based on the study of human cognitive maps, we develop a spatial semantic hierarchical model to replace the global absolute coordinate frame used in traditional approaches. The semantic hierarchical model consists of three levels: control level, topological level, and geometrical level. The topological level provides the basic structure of the hierarchy. At the control level, a robot finds places or follows travel edges which can be described by qualitatively definable features. The distinctive features allow development of distinctiveness measures. The robot uses these measures to find, with negative feedback control, the distinctive places by hill-climbing search algorithms, and the travel edges by edge-following algorithms. Distinctive places and travel edges are connected to build a topological model. This model is created prior to the construction of a global geometrical map. Cumulative location error is essentially eliminated while traveling among distinctive places and travel edges by alternating between the hill-climbing search control algorithms and the edge-following control algorithms. On top of the topological model, metrical information is accumulated first locally and then globally. Using a simulation package with a robot instance, NX, we demonstrate the robustness of our method against sensorimotor errors. The control knowledge for distinctive places and travel edges, the topological matching process, and the metrical matching process with local geometry make our approach robust in the face of metrical errors. In addition to robust navigation at the control and topological levels, our framework can incorporate certain metrically-based methods and thus provide the best of both approaches.

DOWNLOAD UT-AI-TR-90-121.pdf

AI90-141

Hermjakob, Ph.D., Ulf. "Access-Limited Logic -- A Language for Knowledge Representation". The University of Texas at Austin, Department of Computer Sciences. Report# AI90-141 (dissertation). October 1990. 237 pages.

Access-Limited Logic (ALL) is a language for knowledge representation which formalizes the access limitations inherent in a network structured knowledge-base. Where a deductive method such as resolution would retrieve all assertions that satisfy a given pattern, an access-limited logic retrieves all assertions reachable by following an available access path. The time complexity of inference is thus a polynomial function of the size of the accessible portion of the knowledge- base, rather than the size of the entire knowledge-base. Access-Limited Logic, though incomplete, still has a well defined semantics and a weakened form of completeness, Socratic Completeness, which guarantees that for any query which is a logical consequence of the knowledge-base, there exists a series of queries after which the original query will succeed. We have implemented ALL in Lisp and it has been used to build several non-trivial systems, including versions of Qualitative Process Theory and Pearl's probability networks. ALL is a step toward providing the properties - clean semantics, efficient inference, expressive power - which will be necessary to build large, effective knowledge bases.

DOWNLOAD UT-AI-TR-90-141.pdf

AI90-145

Blumenthal, Brad Brand. "Applying Design Replay to the Domain of Metaphoric Human Interface Design". The University of Texas at Austin, Department of Computer Sciences. Report# AI90-145 (dissertation). December 1990. 126 pages.

This research focuses on the development of an algorithm for recording the experience of an automated design system and reusing that experience to improve the performance of the design system on subsequent design episodes. This new design replay algorithm has been implemented in the REMAID system, applied to the domain of automated human interface design, and empirically tested against implementations of other approaches to design replay presented in the literature. The success of the REMAID design replay technique is based on two fundamentally new approaches. First, REMAID effectively interleaves design replay with generic automated design by recognizing and intelligently adapting to various kinds of mismatches between the recorded experience and the current episode. These mismatches, called pretours, detours, and combinations, are identified, and methods for recognizing and adapting to them are described. The second approach used by the REMAID algorithm is to reuse the reasoning involved in producing a design, rather than just the choices. This is implemented by recording and reusing the heuristics used to produce a design, rather than simply recording the goals that were addressed. In particular, the heuristics that were used to order subgoals in a design are recorded and reused. The design system that REMAID is applied to is called MAID and automatically produces human interface designs for a computer application when given a specification of the functionality of that application. In addition to serving as the test domain for REMAID, MAID advanced the state of the art in automated human interface design by implementing a representation and an algorithm that automatically incorporates characteristics from real world objects into interface designs. MAID creates such metaphoric interface designs by importing appearances, new objects and other features suggested by the real-world entity. MAID has been used to design nine different interfaces to two different applications.

DOWNLOAD NOT AVAILABLE

AI90-146

Branting, Karl. "Integrating Rules and Precedents for Classification and Explanation: Automating Legal Analysis". The University of Texas at Austin, Department of Computer Sciences. Report# AI90-146 (dissertation). December 1990. 159 pages.

The goal of this research is to develop a model for problem solving that integrates general rules with specific examples. Developing such a model is important because neither rules nor examples, standing alone, are sufficient for problem solving in many important domains. Few areas of human expertise are so well understood that problem solving is reducible to deduction from general principles. Similarly, there are few domains in which experience is so extensive that every new problem precisely matches a previous problem whose solution is known. When neither rules nor examples are individually sufficient, problem-solving expertise depends on integrating both. Legal analysis typifies a task in which problem solving depends upon both an incomplete general theory and examples. A lawyer familiar only with the literal text of legal rules but ignorant of any examples of their use would be critically handicapped in the tasks of making, anticipating, and evaluating arguments. Much of the expertise of an experienced lawyer comes not from knowledge of legal rules themselves, but from familiarity with examples of the use of rules for argumentation, planning, and adjudication. The dependence of expert performance in law on both rules and examples makes law an ideal domain for illustrating and evaluating models for integrating general and specific knowledge sources.

DOWNLOAD NOT AVAILABLE

TR-90-37

Iscoe, Neil Allen. "Domain-specific Programming: an Object-Oriented and Knowledge-Based Approach to Specification and Generation". University of Texas at Austin, Department of Computer Sciences. Report# TR-90-37 (dissertation). November 1990. 154 pages.

Programmers must have an understanding of both programming knowledge and application domain knowledge to write application programs. But while programming is well enough understood to model and teach, application domain knowledge is not yet well understood, and is codified only in an informal ad hoc manner. Because representations that precisely characterize application domain knowledge do not currently exist, errors are frequently made when gathering and mapping specifications from the informal to the formal. This dissertation defines a meta-model for application domain knowledge and describes a methodology for its instantiation into domain-specific models. Domain models are representations of application domains that can be used for a variety of operational goals in support of specific software engineering tasks or processes. The meta-model and methodology in this dissertation facilitate understanding and analyzing application areas and eliciting and formalizing software requirements and specifications. The emphasis is on general characterization techniques that can be used to instantiate models from different application domains.

DOWNLOAD tr90-37.pdf

TR-90-36

Menon, Vinod. "Dynamic Aspects of Signaling in Distributed Neural Systems". University of Texas at Austin, Department of Computer Sciences. Report# TR-90-36 (dissertation). November 1990. 162 pages.

A distributed neural system consists of localized populations of neurons - neuronal groups - linked by massive reciprocal connections. Signaling between neuronal groups forms the basis of functioning of such a system. In this thesis, fundamental aspects of signaling are investigated mathematically with particular emphasis on the architecture and temporal self-organizing features of distributed neural systems. Coherent population oscillations, driven by exogenous and endogenous events, serve as autonomous timing mechanisms and are the basis of one possible mechanism of signaling. The theoretical analysis has, therefore, concentrated on a detailed study of the origin and frequency-amplitude-phase characteristics of the oscillations and the emergent features of inter-group reentrant signaling. It is shown that a phase shift between the excitatory and inhibitory components of the interacting intra-neuronal-group signals underlies the generation of oscillations. Such a phase shift is readily induced by delayed inhibition or slowly decaying inhibition. Theoretical analysis shows that a large dynamic frequency-amplitude range is possible by varying the time course of the inhibitory signal. Reentrant signaling between two groups is shown to give rise to synchronization, desynchronization, and resynchronization (with a large jump in frequency and phase difference) of the oscillatory activity as the latency of the reentrant signal is varied. We propose that this phenomenon represents a correlation dependent non-Boolean switching mechanism. A study of triadic neuronal group interactions reveals topological effects - the existence of stabilizing (closed loop) and destabilizing (open loop) circuits. The analysis indicates (1) the metastable nature of signaling, (2) the existence of time windows in which correlated and uncorrelated activity can take place, and (3) dynamic frequency-amplitude-phase modulation of oscillations. By varying the latencies, and hence the relative phases of the reentrant signals, it is possible to dynamically and selectively modulate the cross-correlation between coactive neuronal groups in a manner that reflects the mapping topology as well as the intrinsic neuronal circuit properties. These mechanisms, we argue, provide dynamic linkage between neuronal groups thereby enabling the distributed neural system to operate in a highly parallel manner without clocks, algorithms, and central control.

DOWNLOAD tr90-36.pdf

TR-90-28

Deshpande, Sanjay R. "A Theory for Automated Synthesis of Architectures for Repetitive Multi-Rate Algorithms". University of Texas at Austin, Department of Computer Sciences. Report# TR-90-28 (dissertation). August 1990. 230 pages.

A theoretical framework is developed to achieve automated architectural synthesis for data-independent, repetitive, multi-rate algorithms from their behavioral specifications. Multi-rate functions are formally defined. It is shown that systolic architectures for algorithms incorporating multi-rate functions make inefficient use of hardware components and that a multi-clock design style can produce more efficient architectures. A graph-oriented language, called Data Dependency Graphs (DDGs), is introduced to facilitate the specification of multi-rate computations. Computational semantics suitable for multi-rate computations are associated with the nodes and edges of the DDG. A compatible model for function execution by hardware components is proposed. A bus-based architectural scheme is also proposed. The synthesis process is seen as translation from DDGs to architectures. Analytic techniques are introduced to extract design information from the DDGs. Synthesis problems are formulated, and heuristic approaches are suggested for their solution. An implementation of a heuristic synthesis system is described. The implementation is evaluated via experiments.

DOWNLOAD tr90-28.pdf

AI89-102

Bulko, William Charles. "Understanding Coreference in a System for Solving Physics Word Problems(Ph.D. Dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# AI89-102 (dissertation). May 1989. 197 pages.

In this thesis, a computer program (BEATRIX) is presented which takes as input an English statement of a physics problem and a figure associated with it, understands the two kinds of input in combination, and produces a data structure containing a model of the physical objects described and the relationships between them. BEATRIX provides a mouse-based graphic interface with which the user sketches a picture and enters English sentences; meanwhile, BEATRIX creates a neutral internal representation of the picture similar to that which might be produced as the output of a vision system. It then parses the text and the picture representation, resolves the references between objects common to the two data sources, and produces a unified model of the problem world. The correctness and completeness of this model has been validated by applying it as input to a physics problem-solving program currently under development. Two descriptions of a world are said to be coreferent when they contain references to overlapping sets of objects. Resolving coreferences to produce a correct world model is a common task in scientific and industrial problem-solving: because English is typically not a good language for expressing spatial relationships, people in these fields frequently use diagrams to supplement textual descriptions. Elementary physics problems from college-level textbooks provide a useful and convenient domain for exploring the mechanisms of coreference. Because flexible, opportunistic control is necessary in order to recognize coreference and to act upon it, the understanding module of BEATRIX uses a blackboard control structure. The blackboard knowledge sources serve to identify physical objects in the picture, parse the English text, and resolve coreferences between the two. We believe that BEATRIX demonstrates a control structure and collection of knowledge that successfully implements understanding of text and picture by computer. We also believe that this organization can be applied successfully to similar understanding tasks in domains other than physics problem-solving, where data such as the output from vision systems and speech understanders can be used in place of text and pictures.

DOWNLOAD NOT AVAILABLE

AI89-103

Kook, Hyung Joon. "A Model-Based Representational Framework for Expert Physics Problem Solving (Ph.D. Dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# AI89-103 (dissertation). May 1989. 258 pages.

Real-world physics problems are presented in terms of informal, real-world objects and the relationships among them. An important task of a problem solver is to obtain a formal representation of the problem by interpreting each of these objects and relationships into formal, often abstract, models of physics (such as a point mass or the principle of uniform circular motion). Representation of such models has been the main research issue in building APEX (A Physics Expert), a computer program developed for solving elementary physics problems. The main areas of research APEX addresses are ways to represent the conceptual models of the domain, the development of methods to obtain the representation of a problem in terms of these models, and the study of the linkage between the two representations (initial, informal, and internal, formal, problem representations). During APEX's problem solving, the problem is represented in the form of a data connection network, which is progressively augmented by these models in the form of additional network elements. In order to explicate the data conversion scheme between the model instances and the features of objects in the initial problem, the notion of view is presented as an object-level representational framework for connecting the two representations. The view framework also supports multiple representations (i.e., viewing many objects as a single canonical physical object, and one object as many canonical physical objects), handling of incompletely specified problems, and the invertibility of the views (the facility for transferring the results obtained from the internal representations back to the original representations). APEX facilitates the selection of models in two independent modes: a human- guided mode in which models are selected by a human through a user-friendly interface, and a machine-inference mode in which models are selected by a rule-based inference system. This computational framework provides a powerful representational mechanism that allows a finite set of physical principles to be applied to a potentially infinite variety of problems.

DOWNLOAD NOT AVAILABLE

TR-89-35

Barnett III, Benjamin Lewis. "Evaluation and Implementation of Protocols in the Local Area Network Testbed Environment". University of Texas at Austin, Department of Computer Sciences. Report# TR-89-35 (dissertation). November 1989. 261 pages.

This thesis presents the results of the Local Area Network Testbed experience. The design of the testbed, the results of several experiments and the results of a formal protocol analysis are included. Three data link layer protocols for Carrier Sense Multiple Access with Collision Detection (CSMA/CD) bus networks were implemented in the testbed. The performance of these three protocols under several different artificial workloads is compared. The three protocols were the commercially available Ethernet, the Enet II protocol proposed by Molloy, and the Virtual Time CSMA/CD (VTCSMA/CD) protocol proposed by Molle. The three protocols represent three fundamentally different approaches to handling collisions among users of a broadcast channel. Ethernet randomizes retransmission attempts for the conflicting packets in an attempt to minimize the likelihood of successive collisions. Enet II uses a probabilistic algorithm to schedule the retransmissions of conflicting packets to resolve the collision. VTCSMA/CD uses a technique which reduces the initial likelihood of collisions. Enet II is shown to have significantly better variance of delay than Ethernet. VTCSMA/CD has the best variance of delay of the three protocols due to the success of its collision avoidance method. The implementation of Enet II demonstrates that techniques usually reserved for slotted networks can be beneficially employed on their unslotted counterparts. To investigate the adaptation of slotted protocols to unslotted use, a well known slotted Collision Resolution Protocol (CRP), the Gallager First-Come, First-Served (FCFS) protocol, is adapted to unslotted operation and proven to have bounded delay. A second adaptation of the protocol which responds to collisions differently is shown to deadlock. Deadlock detection and recovery methods are presented. A new CRP based on the deadlock recovery method and using information about the location of colliding stations is proposed.

DOWNLOAD tr89-35.pdf

AI88-66

Mooney, Raymond. "A General Explanation-Based Learning Mechanism and Its Application to Narrative Understanding (PhD dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# AI88-66 (dissertation). January 1988. 232 pages.

This report consists of the author's dissertation from the University of Illinois at Urbana-Champaign.

DOWNLOAD UT-AI-TR-88-66.pdf

AI88-72

Holte, Robert Craig. "An Analytical Framework for Learning Systems". The University of Texas at Austin, Department of Computer Sciences. Report# AI88-72 (dissertation). February 1988. 172 pages.

The problem addresses in this thesis is that of defining a set of concepts and techniques that facilitate the comparison and analysis of learning systems. Systems are modelled in terms of certain abstract processes and bodies of information. Different types of systems correspond to different ways of representing the model. Systems of different types are compared using behavior-preserving transformations. Formal definitions are given for "representation" and "generative structure" of a system. These and related concepts, such as "bias" and "implicit knowledge", facilitate the analysis of a system's efficiency and its use of task-specific knowledge.

DOWNLOAD UT-AI-TR-88-72.pdf

AI88-83

Bareiss, Ellis Raymond, Jr. "Protos: A Unified Approach to Concept Representation, Classification, and Learning (Ph.D. Dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# AI88-83 (dissertation). August 1988. 215 pages.

The primary contribution of this research is a unified approach to concept representation, classification, and concept learning. This approach has been implemented as a computer program, Protos, which learns concepts as it performs classification under the guidance of a teacher. The soundness of the approach has been demonstrated by successfully applying Protos to the task of acquiring knowledge for performing heuristic classification at an expert level of proficiency. The Protos approach addresses the complexities of representing, using, and learning natural concepts. These concepts are polymorphic and ill-defined. Most machine learning research is based on inductive learning and deductive classification, which are more suitable for artificial domains (e.g., mathematics) than natural domains (e.g., medicine). In contrast, Protos takes an exemplar-based approach. It represents concepts extensionally as sets of retained exemplars, classifies a new instance by recalling a similar exemplar and explaining its similarity to the instance, and learns when a classification failure indicates that knowledge is missing. Because Protos learns as a byproduct of classification, its performance continually improves. Protos has been experimentally evaluated by training it to diagnose hearing disorders. An expert audiologist trained Protos with 200 cases of hearing disorder. Through this small amount of training, Protos evolved into an expert system whose classification performance was comparable to that of experienced human clinicians.

DOWNLOAD UT-AI-TR-88-83.pdf

AI88-84

Lin, Yow-Jian. "A Parallel Implementation of Logic Programs (Ph.D. Dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# AI88-84 (dissertation). August 1988. 118 pages.

Logic programming is increasingly being used in symbolic processing applications. As the complexity of symbolic computation increases, executing logic programs in parallel is perhaps the only way to meet the computational demands of the next generation computing. Due to implicit representation of parallelism and separation of specification and control, logic programming also offers a possible solution to the problem of utilizing highly parallel architectures. Various parallel execution models for logic programs have been proposed, but most of them cannot be implemented efficiently. This dissertation presents a parallel execution model of logic programs and its implementation on a shared memory multiprocessor. The execution model preserves the don't-know nondeterminism, and follows the generator-consumer approach to exploit AND-parallelism. Unlike many other execution models, this model constructs the data-dependency information dynamically, requires no information from the user, and is able to exploit all the AND-parallelism available in the framework of the generator-consumer approach. Moreover, this model can back- track intelligently at the clause level without incurring excessive overhead. Our implementation of this execution model on the Sequent Balance multiprocessor obtains linear speedup on many programs containing AND-parallelism. Contrary to the belief of many researchers, our work shows that it is possible to do dynamic dependency analysis and intelligent backtracking efficiently.

DOWNLOAD UT-AI-TR-88-84.pdf

TR-88-20

Kim, Hyoung-Joo. "Issues in Object-oriented Database Schemas". University of Texas at Austin, Department of Computer Sciences. Report# TR-88-20 (dissertation). May 1988. 244 pages.

The successful use of database management systems in data-processing applications has created a substantial amount of interest in applying database techniques to such areas as knowledge bases and artificial intelligence (AI), computer-aided design (CAD), and office information systems (OIS). In order to provide the additional semantics necessary to model these new applications, many researchers have adopted the object-oriented programming paradigm to serve as a data model. In order to use the objectoriented approach in a database system, it was necessary to add persistence and sharability to the object-oriented programming paradigm. Several database systems based on this approach are under implementation. Therefore, object-oriented database systems combine the strengths of object-oriented programming languages and conventional database systems. The practical applications of object-oriented databases, such as CAD, AI, and OIS, require the ability to dynamically make a wide variety of changes to the database schema. This process is called schema evolution. We establish a consistent and complete framework of schema evolution. Based on our framework, the MCC ODBS group implemented a schema manager within their prototype object-oriented database system, ORION. On top of the schema manager of ORION, we implemented a graphical schema editor, PSYCHO.

DOWNLOAD tr88-20.pdf

TR-88-11

Adiga, Ashok K. "Performance Modelling of Parallel Computations". University of Texas at Austin, Department of Computer Sciences. Report# TR-88-11 (dissertation). April 1988. 165 pages.

The design of parallel computations involves numerous decisions which effect execution efficiency. The choice of an optimum configuration for a computation on a given architecture is essential for attaining the maximum efficiency in terms of achieved speedup. Some of the relevant factors in the configuration space of a computation include the granularity of a task, the communication model used, choice of dependencies between tasks and the host architecture on which the application is to be run. In this dissertation, we present a model for representing parallel computations which can be used to analyze their performance for various configurations. Our model is an extended Petri Net with facilities to model control and data flow mechanisms, as well as synchronization and communication primitives. A methodology is developed for representing the execution of a computation on a given architecture. The methodology consists of viewing the model as consisting of three distinct submodels (the computation, architecture and mapping submodels) which have standard interfaces between them. Specification of a structured methodology enables the automatic generation of model instances. In addition, it becomes possible to specify a library from which architectures can be selected to determine if they are suitable for a given computation. This modelling technique is then used to study the performance of computations under variations in their configuration parameters, including their actual run-time behavior on various target architectures.

DOWNLOAD tr88-11.pdf

TR-88-04

Kim, Sung Jo. "A General Approach to Multiprocessor Scheduling". University of Texas at Austin, Department of Computer Sciences. Report# TR-88-04 (dissertation). February 1988. 155 pages.

As a variety of general-purpose multiprocessor systems have been recently designed and built, multiprocessor scheduling is becoming increasingly important. Multiprocessor scheduling is a technique to exploit the underlying hardware in a multiprocessor system so that parallelism existing in an application program can be fully utilized and interprocessor communication time can be minimized. Traditionally, most research on multiprocessor scheduling has focused on the development of specific scheduling strategies to take advantage of unique characteristics of a specific multiprocessor system or application program. In this thesis, we define and characterize scheduling techniques and related heuristic mapping algorithms which are applicable to a spectrum of multiprocessor systems and a broad class of application programs. The fundamental idea we use is that multiprocessor scheduling can be regarded as a series of mappings from a computation graph (representing an application program) to a virtual architecture graph (representing an optimal architecture for the program) and eventually to a physical architecture graph (representing a target multiprocessor system). We propose linear clustering and linear cluster merging as effectual heuristics. After linear clustering and merging, the computation graph is transformed into a virtual architecture graph. This graph represents an optimal architecture which compromises between two conflicting goals, minimization of interprocessor communication and maximization of potential parallelism, and satisfies the other goals, throughput enhancement and workload balance, relatively well. Then we develop two efficient scheduling algorithms which map the optimal architecture graph onto a physical architecture graph which may represent either a homogeneous or a heterogeneous multiprocessor system. These algorithms rely not only on local information but also on limited global information. Finally, we present the result of performance evaluation of the mapping algorithms on an Intel iPSC with 32 processors and a Sequent Balance with 10 processors.

DOWNLOAD tr88-04.pdf

TR-87-42

Biswas, Jit. "Techniques and Data Structures for Parallel Resource Management". University of Texas at Austin, Department of Computer Sciences. Report# TR-87-42 (dissertation). November 1987. 200 pages.

NO ABSTRACT

DOWNLOAD tr87-42.pdf

TR-87-36

Bhat, Vivekanand. "Design of the Cadm Based Sort/search/set Engine". University of Texas at Austin, Department of Computer Sciences. Report# TR-87-36 (dissertation). September 1987. 171 pages.

NO ABSTRACT

DOWNLOAD tr87-36.pdf

TR-87-21

Ramakrishnan, Raghunath. "On the Implementation of Data Intensive Logic Programs". University of Texas at Austin, Department of Computer Sciences. Report# TR-87-21 (dissertation). May 1987. 210 pages.

NO ABSTRACT

DOWNLOAD tr87-21.pdf

TR-87-04

Dafni, Gad Joseph. "Design and Performance Evaluation of the Texas Object Based System". University of Texas at Austin, Department of Computer Sciences. Report# TR-87-04 (dissertation). January 1987. 205 pages.

NO ABSTRACT

DOWNLOAD tr87-04.pdf

TR-87-02

Hufnagel, Stephen Peter. "Vertically Partitioned Object-oriented Software Design for Dependability And Good Performance". University of Texas at Austin, Department of Computer Sciences. Report# TR-87-02 (dissertation). January 1987. 156 pages.

NO ABSTRACT

DOWNLOAD tr87-02.pdf

AI86-27

Murray, William R. "Automatic Program Debugging for Intelligent Tutoring Systems (PhD dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# AI86-27 (dissertation). June 1986. 276 pages.

Program debugging is an important part of the domain expertise required for intelligent tutoring systems that teach programming languages. This dissertation explores the process by which student programs can be automatically debugged in order to increase the instructional capabilities of these systems. This research presents 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 potential of a program debugger to automatically debug widely varying novice programs in a nontrivial domain is proportional to its capabilities to reason about computational semantics. By increasing these reasoning capabilities a more powerful and robust system can result. This thesis supports these claims by examining related work in automated program debugging and by discussing the design, implementation, and evaluation of Talus, an automatic debugger for LISP programs. Talus relies on its abilities to reason about computational semantics to perform algorithm recognition, infer code teleology and to automatically detect and correct 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. Empirical evaluation demonstrates that Talus achieves high performance in debugging widely varying student solutions to challenging tasks.

DOWNLOAD UT-AI-TR-86-27.pdf

AI86-32

Murray, William R. "Talus: Automatic Program Debugging for Intelligent Tutoring Systems". The University of Texas at Austin, Department of Computer Sciences. Report# AI86-32 (dissertation). August 1986. 37 pages.

This report summarizes the author's dissertation (AI86-27).

DOWNLOAD UT-AI-TR-86-32.pdf

AI86-39

Korner. Kim. "An Intelligent Remote File Server (PhD Dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# AI86-39 (dissertation). December 1986. 180 pages.

Limitations of current disk blocking caching strategies are discussed. A new model for providing remote file service using knowledge based caching algorithms is proposed. The knowledge based algorithms generate expectations of user process behavior which are used to provide hints to the file server. Surplus resources of the remote file server permit incorporation of these hints into caching algorithms. The research involves gathering trace data from a modified Unix kernel and driven simulation of remote file server models. Comparisons are made between conventional, knowledge based and optimal models. Further applications of knowledge based strategies in operating systems are discussed.

DOWNLOAD UT-AI-TR-86-39.pdf

TR-86-20

Hermenegildo, Manuel V. "An Abstract Machine Based Execution Model for Computer Architecture Design And Efficient Implementation of Logic Programs in Parallel". University of Texas at Austin, Department of Computer Sciences. Report# TR-86-20 (dissertation). August 1986. 268 pages.

NO ABSTRACT

DOWNLOAD tr86-20.pdf

AI85-02

Smith, Michael Kavanaugh. "Knowledge Based Contextual Reference Resolution for Text Understanding (PhD dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# AI85-02 (dissertation). January 1985. 95 pages.

This report extends the concept of reference resolution in a discourse context to cover a broad range of connective inference required for text understanding. Access to all conceptual relations is restricted or facilitated by the context established by preceding text. This contextual filter greatly simplifies the establishment of connections between the surface text and previously instantiated discourse representation. The reference procedure requires a taxonomically organized knowledge base of structured concepts, in the sense of frames and scripts. The procedure selects lexical senses and generates reference candidates, which may be either explicit or implicit in the discourse context. These are matched against constraints imposed by the surface text and a conceptual representation is constructed and integrated with the accumulated discourse structure.

DOWNLOAD UT-AI-TR-85-2.pdf

AI85-05

Levinson, Robert A. "A Self Organizing Retrieval System for Graphs (PhD dissertation)". The University of Texas at Austin, Department of Computer Sciences. Report# AI85-05 (dissertation). May 1985. 89 pages.

This report describes the theory, design and implementation of a graph-based, self-organizing database retrieval system. The system is designed to support the expert problem solving tasks of recall, design and recovery. The fundamental design principle is the production of a partial ordering by the relation subgraph-of. This relation is considered to be equivalent to more- general-than. This document discusses this design from three different levels: an abstract level in which the nodes in the partial ordering are concepts, the implementation level described above (the nodes are graphs), and an application level in which the nodes are domain specific objects such as molecules or reactions. The primary problem domain explored is organic chemistry. A large database of organic reactions and starting materials can be queried to extract reactions or molecules that match, either exactly or approximately, desired structures. The system may also suggest precursors to a desired target molecule. The queries are answered by exploiting a set of concepts that are commonly subgraphs of molecule or reaction graphs. Concepts serve multiple purposes: They constrain the search involved in the matching process so that the time required to answer a query grows sub-linearly in the size of the database. Concepts define the notion of "similarity" that is crucial if approximate match is desired. They also may be useful generalizations of reactions or molecular structures. The concepts can be "discovered" (i.e., constructed) by the system itself using largely syntactic criteria based on the topology of the database. A variety of performance tests are performed, including a comparison of the system's precursor recommendation capability with graduate students in organic chemistry. The system is also applied to the retrieval and generalization of chess positions.

DOWNLOAD NOT AVAILABLE

TR-84-19

Gangopadhyay, Dipayan. "A Formal System for Network Databases and Its Applications to Integrity Related Issues". University of Texas at Austin, Department of Computer Sciences. Report# TR-84-19 (dissertation). June 1984. 113 pages.

NO ABSTRACT

DOWNLOAD tr84-19.pdf

TR-84-18

Struensee, Michael Calvin. "Uses of Dipole Oscillator Strength Sum Rules in Second Order". University of Texas at Austin, Department of Computer Sciences. Report# TR-84-18 (dissertation). June 1984. 192 pages.

NO ABSTRACT

DOWNLOAD tr84-18.pdf

TR-84-09

Rathi, Bharat Deep. "The Design and Performance Analysis of a Self Managing Secondary Memory". University of Texas at Austin, Department of Computer Sciences. Report# TR-84-09 (dissertation). March 1984. 201 pages.

NO ABSTRACT

DOWNLOAD tr84-09.pdf

TR-83-230

Han, Sang Yong. "A Language for the Specification and Representation of Programs in a Data Flow Model of Computation". University of Texas at Austin, Department of Computer Sciences. Report# TR-83-230 (dissertation). May 1983. 213 pages.

NO ABSTRACT

DOWNLOAD NOT AVAILABLE

TR-83-228

Canas, Daniel A. "Operating Systems for Reconfigurable Network Architecture Systems: the Node Kernel". University of Texas at Austin, Department of Computer Sciences. Report# TR-83-228 (dissertation). May 1983. 143 pages.

NO ABSTRACT

DOWNLOAD tr83-228a.pdf tr82-228b.pdf tr82-228c.pdf

TR-83-216

Kunii, Hideko. "Graph Data Language: a High Level Access-path Oriented Language". University of Texas at Austin, Department of Computer Sciences. Report# TR-83-216 (dissertation). May 1983. 188 pages.

NO ABSTRACT

DOWNLOAD tr83-216.pdf

TR-82-209

Alterman, Richard Ethan. "A System of Seven Coherence Relations for Hierarchically Organizing Event Concepts in Text". University of Texas at Austin, Department of Computer Sciences. Report# TR-82-209 (dissertation). September 1982. 184 pages.

NO ABSTRACT

DOWNLOAD tr82-209a.pdf tr82-209b.pdf tr82-209c.pdf tr82-209d.pdf

TR-82-25

DiVito, Benedetto L. "Verification Of Communications Protocols And Abstract Process Models". The University of Texas at Austin, Department of Computer Sciences. Report# TR-82-25 (dissertation). August 1982. 243 pages.

Communications protocols are crucial for the reliable exchange of information in distributed systems. In this dissertation, we consider the problem of formally specifying and verifying properties of protocol systems. Such systems are modeled by hierarchies of concurrent processes, where interprocess communication is achieved by message passing rather than through arbi trary shared variables. Based on this model, a methodology is developed for mechanically assisted protocol analysis. The Gypsy methodology for concurrent program verification is the point of departure for much of this work. Specialized methods applicable to protocols are derived from the Gypsy methods. Behavior of protocol modules is specified in a fairly abstract manner using a state transition paradigm, thus avoiding a highly procedural form of specification. Protocol services are specified by means of assertions over message histories. Proof techniques are introduced for verifying safety properties of the proc~ss models. In addition, a specification and assertion language is developed. This language emphasizes features and operations useful for expressing protocol oriented concepts and constructing proofs about them. An important aspect of this work is use of machine assisted analysis, most notably the use of mechanical theorem proving. A strategy for applying a particular automatic theorem prover, the Boyer-Moore prover, to protocol verification problems is put forth. A consequence of this strategy is the accumulation of a large body of proved lemmas, constituting a rudimentary deductive theory for protocols. With this theory, the methodology has successfully been applied to a pair of sample transport protocols. These include the Stenning protocol and an abstraction of the data transfer function of Tep.

DOWNLOAD tr82-25.pdf

TR-81-177

Burger, Wilhelm F. "A Modeling System for Mathematical Programming". University of Texas at Austin, Department of Computer Sciences. Report# TR-81-177 (dissertation). May 1981. 112 pages.

NO ABSTRACT

DOWNLOAD tr81-177.pdf

TR-80-164

Amsler, R. A. "The Structure of the Merriam-Webster Pocket Dictionary". University of Texas at Austin, Department of Computer Sciences. Report# TR-80-164 (dissertation). December 1980. 175 pages.

NO ABSTRACT

DOWNLOAD tr80-164a.pdf tr80-164b.pdf tr80-164c.pdf

TR-80-154

Smith, Connie U. "The Prediction and Evaluation of the Performance of Software From Extended Design Specificatoins". University of Texas at Austin, Department of Computer Sciences. Report# TR-80-154 (dissertation). August 1980. 148 pages.

NO ABSTRACT

DOWNLOAD tr80-154a.pdf tr80-154b.pdf tr80-154c.pdf

TR-76-57

Keller, T. W. "Computer System Models with Passive Resources". University of Texas at Austin, Department of Computer Sciences. Report# TR-76-57 (dissertation). May 1976. 82 pages.

NO ABSTRACT

DOWNLOAD tr76-57.pdf tr76-57a.pdf

TR-75-48

Foster, D. V. "File Assignment in Memory Hierarchies". University of Texas at Austin, Department of Computer Sciences. Report# TR-75-48 (dissertation). May 1975. 137 pages.

NO ABSTRACT

DOWNLOAD tr75-48a.pdf tr75-48b.pdf

TR-74-39

Baldwin, L. J. "A Method for Designing Programs and Its Application to Introductory Computer Science Courses". University of Texas at Austin, Department of Computer Sciences. Report# TR-74-39 (dissertation). August 1974. 138 pages.

NO ABSTRACT

DOWNLOAD tr74-39a.pdf tr74-39b.pdf

TR-74-35

Alexander III, W. P. "Analysis of Sequencing in Computer Programs and Systems". University of Texas at Austin, Department of Computer Sciences. Report# TR-74-35 (dissertation). August 1974. 92 pages.

NO ABSTRACT

DOWNLOAD tr74-35a.pdf tr74-35b.pdf tr74-35c.pdf

TR-74-32

Anderson, J. W. "Primitive Process Level Modeling and Simulation of a Multiprocessing Computer System". University of Texas at Austin, Department of Computer Sciences. Report# TR-74-32 (dissertation). May 1974. 123 pages.

NO ABSTRACT

DOWNLOAD tr74-32a.pdf tr74-32b.pdf tr74-32c.pdf

TR-73-20

Friedman, D. P. "Grope: a Graph Processing Language and Its Formal Definition". University of Texas at Austin, Department of Computer Sciences. Report# TR-73-20 (dissertation). August 1973. 136 pages.

NO ABSTRACT

DOWNLOAD tr73-20.pdf

TR-73-18

Ragland, L. C. "A Verified Program Verifier". University of Texas at Austin, Department of Computer Sciences. Report# TR-73-18 (dissertation). May 1973. 157 pages.

NO ABSTRACT

DOWNLOAD tr73-18.pdf

ATP-5

Boyer, Robert. "Machine Locking: A Restriction Of Resolution". The University of Texas at Austin, Department of Computer Sciences. Report# ATP-5 (dissertation). August 1971. 81 pages.

Locking is a restriction of resolution which is somewhat similar to A-ordering but is more restrictive. It involves arbitrarily indexing with integers the literals in the clauses to be resolved; different occurrences of the same literal may be indexed differently. Resolution is then permitted only on literals of lowest index in each clause. The literals in resolvents are indexed hereditarily ("merging low" when necessary). It is shown to be complete for first order logic. Locking results in a significant reduction in the number of clauses generated (as compared with ordinary resolution). In this thesis locking is compared with other restrictions of resolution and is shown to be incompatible with some. It is not compatible with linear format and merging, but this shortcoming seems to be more than compensated for by the fact that both clauses are restricted in every resolution. Several examples of locking derivations are given. Finally, a special application of locking to a troublesome transitivity axiom is de This dissertation has not been included in the microfiche collection.

DOWNLOAD atp5.pdf

AI82-25

DiVito, Benedetto L. "Verification Of Communications Protocols And Abstract Process Models". The University of Texas at Austin, Department of Computer Sciences. Report# AI82-25 (dissertation). August 1982. 243 pages.

Communications protocols are crucial for the reliable exchange of information in distributed systems. In this dissertation, we consider the problem of formally specifying and verifying properties of protocol systems. Such systems are modeled by hierarchies of concurrent processes, where interprocess communication is achieved by message passing rather than through arbi trary shared variables. Based on this model, a methodology is developed for mechanically assisted protocol analysis. The Gypsy methodology for concurrent program verification is the point of departure for much of this work. Specialized methods applicable to protocols are derived from the Gypsy methods. Behavior of protocol modules is specified in a fairly abstract manner using a state transition paradigm, thus avoiding a highly procedural form of specification. Protocol services are specified by means of assertions over message histories. Proof techniques are introduced for verifying safety properties of the proc~ss models. In addition, a specification and assertion language is developed. This language emphasizes features and operations useful for expressing protocol oriented concepts and constructing proofs about them. An important aspect of this work is use of machine assisted analysis, most notably the use of mechanical theorem proving. A strategy for applying a particular automatic theorem prover, the Boyer-Moore prover, to protocol verification problems is put forth. A consequence of this strategy is the accumulation of a large body of proved lemmas, constituting a rudimentary deductive theory for protocols. With this theory, the methodology has successfully been applied to a pair of sample transport protocols. These include the Stenning protocol and an abstraction of the data transfer function of Tep.

DOWNLOAD tr82-25.pdf

AI82-1

Alterman, Richard E. "A System of Seven Coherence Relations for Hierarchically Organizing Event Concepts in Text". The University of Texas at Austin, Department of Computer Sciences. Report# AI82-1 (dissertation). December 1982.

A theory of event concept coherence is developed. It is shown that the pieces of event description which appear in a body of text can be gathered together and hierarchically organized using a dictionary of event/state concepts. This theory has been implemented in a computer system, NEXUS. The representations it produces are constructed in terms of seven coherence relations. The dictionary it uses was compiled from an analysis of ten folk tales. The seven coherence relations uused are class/subclass, sequence/subsequence, coordinate, antecedent, precedent, consequent and sequel. Sequence/subsequence and coordinate are two kinds of whole/part relations. The other four relations are temporal; antecedent and precedent concepts come before an event, consequent and sequel concepts come after an event. Associations between concepts in the dictionary are also organized in terms of the seven coherence relations. Associated with the concepts in the dictionary are default values for its case related arguments. Relationships between concepts in the dictionary are refined by attaching to each relationship in the dictionary a set of constraints on matching case arguments. NEXUS uses the default values and the constraints to control the representation building process. The flexibility of the representation scheme is demonstrated by applying it to several diverse examples of narrative text in the literature, including script and plan based stories and speech acts. The feasibility of NEXUS is shown by applying it to eight samples of text and discussing in detail the results. The utility of the hierarchical representation produced by NEXUS is validated by experiments in question answering and summarizing. CS-TR-209. This dissertation has not been included in the microfiche collection.

DOWNLOAD NOT AVAILABLE

AI81-2

Tyson, W. Mabry. "APRVR: A Priority-Ordered Agenda Theorem Prover". The University of Texas at Austin, Department of Computer Sciences. Report# AI81-2 (dissertation). August 1981.

This dissertation is concerned with research in automatic theorem proving by computers. Discussed herein are issues involved with designing a natural deduction theorem proving system whose search is guided by the priorities assigned to the formulas it attempts to prove and the methods used to prove them. A list of the tasks to be done is kept in an agenda ordered by these priorities. A particular implementation of a priori ty-ordered agenda theorem prover, named APRVR, is described but the main purpose of the research is to explore the advantages and problems of using search strategy for theorem proving. The first chapter introduces theorem proving in general, and natural deduction theorem proving in particular. The need for a new combination of search strategy and control structure is motivated and the agenda-based system is shown to fill this need. The objective of the research for this dissertation is set. Providing the groundwork for the later chapters, the second chapter describes the proof methods of t The examples given to APRVR are described in Chapter 5 and include some problems from symbolic logic, set theory and group theory. The final example is a linear real inequality that has never before been proved by machine. APRVR's performance on these examples is discussed. Example proofs are included in an appendix. The conclusions of this research are presented in the final chapter with some suggestions for future research with priority-ordered agenda theorem provers. ATP-66. This dissertation has not been included in the microfiche collection.

DOWNLOAD NOT AVAILABLE

AI81-1

Slocum, Jonathan. "A Practical Comparison of Parsing Strategies for Machine Translation and Other Natural-Language Processing Purposes". The University of Texas at Austin, Department of Computer Sciences. Report# AI81-1 (dissertation). 1981.

Twelve parsing methods are compared in a practical setting, using three distinct grammars covering significant subsets of English, or German, in a series of experiments involving substantial texts drawn from independent sources. The purposes for which the various grammars were written and the approximate event of coverage for each grammar are described to support the claim that the comparison is meaningful and indicative of general, average-case performance. The parsing strategies and the measurement techniques are discussed in some detail. The results are sometimes counter-intuitive, and differ from theoretical performance predictions. Discussion centers on the interpretation of the results, including how the choice of evaluation metric affects performance judgments. Conclusions are drawn about the relative efficiencies of these methods in real-world settings, and the significance of previous theoretical and idealized accounts of parser performance in light of the results obtained. NL-41. This dissertation has not been included in the microfiche collection.

DOWNLOAD NOT AVAILABLE

AI80-1

Roach, J. W. "Determining the Three-Dimensional Motion and Model of Objects from a Sequence of Images". The University of Texas at Austin, Department of Computer Sciences. Report# AI80-1 (dissertation). October 1980. 157 pages.

The goal of this dissertation is to determine precisely how an object is moving in three-dimensional space and to determine the three-dimensional- relationship of points on the surface of the object. The only information available is a sequence of photographic images taken as the object moves across the field of view. The problem can be broken down into two sub-problems: the problem of determining the correspondence of feature points in one image with feature points in the next image; and once the correspondence is established, the mathematical analysis required to determine the model and the movement. The correspondence problem, i.e., matching, is investigated using images of moving blocks. The corners of the blocks constitute the feature points to be put in correspondence between images. Several matching methods are combined into a hierarchy so that if one method fails another method can take over to help complete the matching process. The top level of the hierarchy matches by searching for feature points in the image of expected positions as computed from the expected movement of the object. The next hierarchy level matches an object by its position relative to other objects in the image, a property that is assumed to change only gradually. The next hierarchy level matches a block's faces by relative position. Once faces have been matched, feature points bordering the faces not already matched by expected position can be put in correspondence. The mathematical analysis of the problem shows that there are an infinite number of geometrically similar solutions, each solution differing from the others by a scaling factor. A specific solution can be found by setting the scaling to an arbitrary number. Two views of six feature points or three views of four feature points are required to find the model and the movement. For good accuracy, however, considerably more points, two views of twelve or fifteen points for example, are needed. Also available as TR80-02.

DOWNLOAD tr80-2.pdf

AI79-16

Hare, Dwight Francis. "A Structure Program for the Gypsy Verification Environment". The University of Texas at Austin, Department of Computer Sciences. Report# AI79-16 (dissertation). August 1979. 112 pages.

NO ABSTRACT

DOWNLOAD UT-AI-TR-79-16.pdf

AI76-nl30

Novak, Gordon S., Jr. "Computer Understanding of Physics Problems Stated in Natural Language. (Dissertation), also Technical Report NL-30". The University of Texas at Austin, Department of Computer Sciences. Report# AI76-nl30 (dissertation). March 1976. 120 pages.

This thesis describes a computer program, called ISAAC, which can read, understand, solve, and draw pictures of physics problems stated in English. The program has solved twenty problems, most of which were taken unedited from high school and college physics texts. These problems involve rigid bodies in static equilibrium, and include such objects as levers, pivots, weights, ropes, and springs in various configurations. An example of the class of problems solved is the following (from Schaum's Outline of College The foot of a ladder rests against a vertical wall and on a horizontal floor. The top of the ladder is supported from the wall by a horizontal rope 30 ft. long. The ladder is 50 ft. long, weighs 100 lb. with its center of gravity 20 ft. from the foot, and a 150 lb. man is 10 ft. from the top. Determine the tension in the rope. In order to understand and solve such a problem, it is necessary to build an internal model of the problem in which the various objects and their interrelationships are adequately represented. Many of the relationships and features of the objects are not specified explicitly in the problem statement, but must be inferred by using common sense knowledge of what is usual. In the above example, we assume that the man is standing on the ladder although this is not explicitly stated. Thus, the understanding of a physics problem is an active process in which the sentences of the problem statement are used to guide the construction of a mode which represents the relationships and features of objects with much greater detail and specificity than they are specified in the original problem statement. In this thesis, we investigate ways in which the meanings of phrases and sentences may be understood and related to a developing model of the problem, using common sense knowledge (represented by computer programs) to aid the understanding process. Ways of representing objects and their relationships are developed. These representations, which are originally created in response to the sentences in the problem statement, are further elaborated by processes which construct a geometric model of the problem, associate canonical objects (such as a point mass) with physical objects (such as a person), write and solve equations which describe the interactions of the objects, and construct a diagram of the problem. The techniques used in ISAAC have potential application in providing a natural-language interface between specialist programs and users who are not computer professionals, and in computer programs. for teaching physics and other technical subjects. This dissertation has not been included in the microfiche.

DOWNLOAD nl-30.pdf

AI75-1

Hendrix, Gary G. "Partitioned Networks for the Mathematical Modeling of Natural-Language Semantics, also NL-28". The University of Texas at Austin, Department of Computer Sciences. Report# AI75-1 (dissertation). 1975.

The main concern of this dissertation is to advance a modeling scheme for use in artificially intelligent natural-language understanding which is capable of encoding knowledge about the world in a uniform, precise and easily manipulatable form. As a prerequisite to understanding, fundamental concepts such as time, space, relation and change are formalized in terms of set-theoretic constructs. Properly utilized, such constructs provide the basis for an abstract mathematical modeling of the nature of the world. Certain human-like organization schemes are imposed upon the set-theoretic models so that knowledge becomes grouped into bundles which are meaningful and convenient units for discourse. The organization schemes include a hierarchical classification, of objects and the packaging of sets of related changes into units called processes. Processes are defined by "process automata," structures capable of encoding discrete, continuous and parallel change. In conjunction with the hierarchy, process automata may be used to describe certain objects (both events and physical objects) at multiple levels of detail. Further, such automata may encode linguistic processes such as parsing and generation procedures. To facilitate use by computers, the set-theoretic modeling scheme is mapped onto a network representation. This network representation provides easily accessible cross-linkage between semantically related pieces of information, thus facilitating algorithms which interrogate the information modeled in the network. A special network partitioning mechanism is used to delimit the scopes of quantified variables, to distinguish hypothetical and imaginary situations from reality, to encode the multiple, alternative worlds considered in planning, and to focus attention at particular levels of detail. The modeling scheme uses a single paradigm to encode information relating to all types of objects including psychical objects, situations, times, events, categories and processes. NL-28. This dissertation has not been included in the microfiche collection.

DOWNLOAD NOT AVAILABLE

AI73-1

Friedman, Daniel P. "GROPE: A Graph Processing Language and its Formal Definition". The University of Texas at Austin, Department of Computer Sciences. Report# AI73-1 (dissertation). August 1973.

This dissertation concerns the design of a programming language for efficient processing of directed graph data structures and the precise formal definition of the semantics of the language designed. The design handles data structures and operations rather than control structures. This emphasis at the semantics level gives rise to a somewhat different view of the problem of formal definition. This research has resulted in the development of a graph processing language, GROPE, for efficient processing of directed graph structures. GROPE embodies some major new ideas about representation and processing of complex data structures. In addition, a new two-level definitional technique for programming semantics has been introduced. One level develops user-oriented semantics and the other develops implementation-oriented semantics. As an illustration of this technique a major part of GROPE is formally defined. CS-TR-20. This dissertation has not been included in the microfiche collection.

DOWNLOAD NOT AVAILABLE

For help please contact trcenter@cs.utexas.edu