A two-step method is presented for verifying that safety properties are not violated by an HMS (hierarchical multistate) specification of a system. In the first step, the question of safety verification is recast as a reachability problem in an extension of the HMS machine. In the second step, reachability is determined by the use of correctness-preserving and partial correctness-preserving transformations. The method is shown to be complete, and it is illustrated by verifying that a safety property holds for a simple railroad-crossing system if all of its deadlines are met.>

A state-based specification methodology for real-time systems is presented that reduces the number of states by orders of magnitude compared to standard techniques and provides explicit representation for temporal constraints. Formal definitions and a graphic notation for the associated hierarchical multistate (HMS) machines are presented, and various concepts of hierarchy of HMS machines are explored. A promising approach to reusability of specifications using generic nondeterministic HMS machines is introduced. Some preliminary results are presented on the formal verification of properties of an HMS machine by (1) extending it to represent requirements as new states and (2) performing reachability analysis on the extended machine to prove the consistency of the requirements with the original specification.>

The notion of a qualified function is introduced as a general means of representing the parameters of dynamic systems. Two specific types of qualified functions are defined for the analysis of the behavior and performance of structured programs. Transformation functions represent the values of variables during execution and timing algorithms express the execution times of programs symbolically. Complete rules of derivation for transformation functions and timing algorithms are given for the control mechanisms of sequence, selection, fixed loop, and while statement. Deterministic and stochastic simplification of transformation functions and timing algorithms are investigated and methods of eliminating recursion for expressions corresponding to while statements are studied.

A new system of numerals is introduced for representing numbers in base 2Nfor N≤8. The new notation greatly simplifies arithmetical operations on numbers. For examples for, N=3(4) one obtains a notation for octal (hexadecimal) numbers in which one can perform addition and multiplication much more easily than in the standard notation. For N=8 one obtains a practical way of representing numbers to the base 256. A simplification of the decimal notation is also presented.

A solution is presented for the following problem: Determine a procedure that produces, for each full trio L of context-free languages (more generally, each trio of r.e. languages), a family of context-free (phrase structure) grammars which (a) defines L, (b) is simple enough for practical and theoretical purposes, and (c) in most cases is a subfamily of a well-known family of context-free (phrase structure) grammars for L if such a well-known family exists. (A full trio (trio) is defined to be a family of languages closed under homomorphism (ε-free homomorphism), inverse homomorphism, and intersection with regular sets.) The key notion in the paper is that of a grammar schema. With each grammar schema there is associated a family of interpretations. In turn, each interpretation of a grammar schema gives rise to a phrase structure grammar. Given a full trio (trio) L of context-free (r.e.) languages, one constructs a grammar schema whose interpretations (ε-limited interpretations) then give rise to the desired family of grammars for L.

Families of acceptors, called SS-AFA, are introduced in which the storage structure is of a very general form. For example, SS-AFA include ordinary AFA and all known multitape AFA, as well as families of acceptors whose storage structure is an n-dimensional array, a tree, or a linked structure. It is shown that from the point of view of languages defined, SS-AFA are equivalent to ordinary AFA.