Systems consisting of several finite components that communicate via unbounded perfect FIFO channels (i.e., FIFO systems) arise naturally in modeling distributed systems. Despite well-known difficulties in analyzing such systems, they are of significant interest as they can describe a wide range of communication protocols. In this article, we study the problem of computing the set of reachable states of a FIFO system composed of piecewise components. This problem is closely related to calculating the set of all possible channel contents, that is, the limit language , for each control location. We present an algorithm for calculating the limit language of a system with a single communication channel. For multichannel systems, we show that the limit language is piecewise if the initial language is piecewise. Our construction is not effective in general; however, we provide algorithms for calculating the limit language of a restricted class of multichannel systems in which messages are not passed around in cycles through different channels. We show that the worst case complexity of our algorithms for single-channel and important subclasses of multichannel systems is exponential in the size of the initial content of the channels.

Systems consisting of several components that communicate via unbounded perfect FIFO channels (i.e. FIFO systems) arise naturally in modeling distributed systems. Despite well-known difficulties in analyzing such systems, they are of significant interest as they can describe a wide range of communication protocols. Previous work has shown that piecewise languages play an important role in the study of FIFO systems. In this paper, we present two algorithms for computing the set of reachable states of a FIFO system composed of piecewise components. The problem of computing the set of reachable states of such a system is closely related to calculating the set of all possible channel contents, i.e. the limit language. We present new algorithms for calculating the limit language of a system with a single communication channel and a class of multi-channel system in which messages are not passed around in cycles through different channels.We show that the worst case complexity of our algorithms for single-channel and important subclasses of multichannel systems is exponential in the size of the initial content of the channels.

We present a new tool, named DART, for automatically testing software that combines three main techniques: (1) automated extraction of the interface of a program with its external environment using static source-code parsing; (2) automatic generation of a test driver for this interface that performs random testing to simulate the most general environment the program can operate in; and (3) dynamic analysis of how the program behaves under random testing and automatic generation of new test inputs to direct systematically the execution along alternative program paths. Together, these three techniques constitute Directed Automated Random Testing, or DART for short. The main strength of DART is thus that testing can be performed completely automatically on any program that compiles -- there is no need to write any test driver or harness code. During testing, DART detects standard errors such as program crashes, assertion violations, and non-termination. Preliminary experiments to unit test several examples of C programs are very encouraging.

Composing text on the computer is usually heavily dependent on editing, such as moving text around, correcting spacing, and inserting punctuation characters. Dictation systems, based on automatic speech recognition, are not known for their efficiency as an editing tool - something that significantly reduces their potential for freeing the user from the keyboard. Speech recognition has almost invariably been tied to natural language, but we point out that this approach is inherently disadvantageous in important ways. Instead, given the evidence that humans routinely become experts at sequencing signs not related to natural language, we propose that editing command languages should rely on symbolizations similar to that of the keyboard. We introduce ShortTalk, an editing language whose command sequences are primitive symbol combinations that are not confusable with dictation. We argue that ShortTalk by construction may solve common editing situations much more efficiently than by use of keyboard and mouse. Our experimental results for ShortTalk indicate that an average information rate of about 16 bit/s for editing commands is achievable. Thus, editing by speech may be more efficient than by non-verbal means.

Composing text on the computer is usually heavily dependent on editing, such as moving text around, correcting spacing, and inserting punctuation characters. Dictation systems, based on automatic speech recognition, are not known for their efficiency as an editing tool-something that significantly reduces their potential for freeing the user from the keyboard. Speech recognition has almost invariable been tied to natural language, but we point out that this approach is inherently disadvantageous in important ways. Instead, given the evidence that humans routinely become experts at sequencing signs not related to natural language, we propose that editing command languages should rely on symbolizations similar to that of the keyboard. We introduce ShortTalk, an editing language whose command sequences are primitive symbol combinations that are not confusable with dictation. We argue that ShortTalk by construction may solve common editing situations much more efficiently than by use of keyboard and mouse. Our experimental results for ShortTalk indicate that an average information rate of about 16 bps for editing commands is achievable. Thus, editing by speech may be more efficient than by non-verbal means.

Rich and interactive multimedia applications, where audio, video, graphics and text are precisely synchronized under timing constraints are becoming ubiquitous. Multimodal applications further extend the concept of user interaction combining different modalities, like speech recognition, speech synthesis and gestures. However, authoring dialog-capable multimodal, multimedia services is a very difficult task. Fortunately, the W3C has sponsored the development of SMIL, an elegant notation for multimedia applications, which has been embraced by both Microsoft and RealNetworks. In this paper, we argue that SMIL is an ideal substrate for extending multimedia applications with multimodal facilities. SMIL as it stands is not a general notation for controlling media and input mode resources. We show that all what is needed are few natural extensions to SMIL along with the addition of a simple reactive programming language that we call ReX. Our language is designed to be maximally compatible with existing W3C recommendations through a generic event system based on DOM and an expression language based on XPATH. It is also designed to be simple so that the fundamental notion of seeking time (e.g. going backwards and forwards in presentations) is preserved.

We propose a novel high level programming notation, called FIDO, that we have designed to concisely express regular sets of strings or trees. In particular, it can be viewed as a domain-specific language for the expression of finite state automata on large alphabets (of sometimes astronomical size). FIDO is based on a combination of mathematical logic and programming language concepts. This combination shares no similarities with usual logic programming languages. FIDO compiles into finite state string or tree automata, so there is no concept of run-time. It has already been applied to a variety of problems of considerable complexity and practical interest. We motivate the need for a language like FIDO, and discuss our design and its implementation. Also, we briefly discuss design criteria for domain-specific languages that we have learned from the work with FIDO. We show how recursive data types, unification, implicit coercions, and subtyping can be merged with a variation of predicate logic, called the Monadic Second-order Logic (M2L) on trees. FIDO is translated first into pure M2L via suitable encodings, and finally into finite state automata through the MONA tool.

We present a technique for automatic verification of pointer programs based on a decision procedure for the monadic second-order logic on finite strings.We are concerned with a while-fragment of Pascal, which includes recursively-defined pointer structures but excludes pointer arithmetic.We define a logic of stores with interesting basic predicates such as pointer equality, tests for nil pointers, and garbage cells, as well as reachability along pointers.We present a complete decision procedure for Hoare triples based on this logic over loop-free code. Combined with explicit loop invariants, the decision procedure allows us to answer surprisingly detailed questions about small but non-trivial programs. If a program fails to satisfy a certain property, then we can automatically supply an initial store that provides a counterexample.Our technique had been fully and efficiently implemented for linear linked lists, and it extends in principle to tree structures. The resulting system can be used to verify extensive properties of smaller pointer programs and could be particularly useful in a teaching environment.

Large software systems are often built on system platforms that support or enforce specific characteristics of the source code or actual design. These characteristics are either captured informally in design guideline documents or in specialized design and implementation languages.In our view, both approaches are unsatisfactory. Informal descriptions do not allow automated analysis and lead to vague constraint descriptions. The language-based approach leads to different languages for different platforms and even for different versions of the same basic platform.Our approach is to describe and name the constraints separately in a design constraint language called CDL, which is based on an extraordinarily concise logic of parse trees. Designs are then annotated with the names of the constraints they are supposed to satisfy.We discuss how the design constraint language is integrated into a design language environment. We exhibit industrial and experimental evidence that our choice of design constraint language allows us to formalize naturally and succinctly common design characteristics.

We propose a new and practical framework for integrating the behavioral reasoning about distributed systems with model-checking methods.

Recursive data structures are abstractions of simple records and pointers. They impose a shape invariant, which is verified at compile-time and exploited to automatically generate code for building, copying, comparing, and traversing values without loss of efficiency. However, such values are always tree shaped, which is a major obstacle to practical use.We propose a notion of graph types, which allow common shapes, such as doubly-linked lists or threaded trees, to be expressed concisely and efficiently. We define regular languages of routing expressions to specify relative addresses of extra pointers in a canonical spanning tree. An efficient algorithm for computing such addresses is developed. We employ a second-order monadic logic to decide well-formedness of graph type specifications. This logic can also be used for automated reasoning about pointer structures.

Using the concept of a progress measure, a simplified proof is given of M.O. Rabin's (1969) fundamental result that the languages defined by tree automata are closed under complementation. To do this, it is shown that for infinite games based on tree automata, the forgetful determinacy property of Y. Gurevich and L. Harrington (1982) can be strengthened to an immediate determinacy property for the player who is trying to win according to a Rabin acceptance condition. Moreover, a graph-theoretic duality theorem for such acceptance conditions is shown. Also presented is a strengthened version of S. Safra's (1988) determinization construction. Together these results and the determinacy of Borel games yield a straightforward method for complementing tree automata.>

Floyd's method based on well-orderings is the standard approach to proving termination of programs.Much attention has been devoted to generalizing this method to termination of programs that are subjected to fairness constraints.Earlier methods for fair termination tend to be somewhat indirect, relying on program transformations, which reduce the original problem to several termination problems.In this paper we introduce the new concept of stack assertions, which directly-without transformationsquantify progress towards fair termination.Moreover, we show that by one simple program transformation of adding a history variable, usual assert ional logic, without jixed-point operators, is sufficiently expressive to form a sound and relatively complete method when used with stack assertions.This result is obtained as part of a substantial simplification of earlier completeness proofs.

A new approach to complementing omega -automata, which are finite-state automata defining languages of infinite words, is given. Instead of using usual combinatorial or algebraic properties of transition relations, it is shown that a graph-theoretic approach based on the notion of progress measures is a potent tool for complementing omega -automata. Progress measures are applied to the classical problem of complementing Buchi automata, and a simple method is obtained. The technique applies to Streett automata, for which an optimal complementation method is also obtained. As a consequence, it is seen that the powerful temporal logic ETLs is much more tractable than previously thought. >

Rabin conditions are a general class of properties of infinite sequences that encompass most known automata-theoretic acceptance conditions and notions of fairness. It is shown how to determine whether a program satisfies a Rabin condition by reasoning about single transitions instead of infinite computations. A concept, a Rabin measure, which in a precise sense expresses progress for each transition towards satisfaction of the Rabin condition, is introduced. When applied to termination problems under fairness constraints, Rabin measures constitute a simpler verification method than previous approaches, which often are syntax-dependent and require recursive applications of proof rules to syntactically transformed programs. Rabin measures also generalize earlier automata-theoretic verification methods. Combined with a result by S. Safra (1988), the result gives a method for proving that a program satisfies a nondeterministic Buchi automaton specification.>