A genetic splicing system involves DNA molecules mixed with enzymes and a ligase that allow the molecules to be cleaved and recombined to produce other molecules in addition to the original ones. Recently, using formal language theory, several researchers have investigated the string properties of DNA molecules that may potentially arise from the original set of molecules under the effect of the given restriction enzymes. This paper introduces an algorithm which, given a splicing system whose initial set of strings is regular, constructs a finite state automaton that recognizes the set of DNA molecules spliced by the system. This algorithm solves the open problem of constructing such an automaton and shows a direct approach to the proof of regularity of spliced languages.

A locally testable language is a language with the property that, for some positive integer j, whether or not a string x is in the language depends on (1) the prefix and suffix of x of length $j - 1$, and (2) the set of substrings of x of length j, without regard to the order in which these substrings occur or the number of times each substring occurs. For any j for which this is true, it is said that the language is j -testable For a given locally testable language, the smallest such number j is called the order of the language. Locally testable languages are regular and therefore these concepts apply to the finite automata that recognize the languages. The authors show that computing the order of a given locally testable deterministic automaton is NP-hard and present a polynomial-time $ \epsilon $-approximation algorithm for computing it. In addition, an upper bound of $2n^2 + 1$ on the order of a locally testable automaton of n states is obtained, and the co-NP-completeness of the problem of whether, for a given j, a given deterministic automaton is j -testable is proven.

The local testability problem of deterministic finite automata is investigated. A locally testable language is a language with the property that, for some nonnegative integer k, whether or not a word w is in the language depends on (1) the prefix and suffix of w of length k, and (2) the set of substrings of w length k+1, without regard to the order in which these substrings occur. The local testability problem is, given a deterministic finite automation, to decide whether or not it accepts a locally testable language. The authors present an O(n/sup 2/) time algorithm for the local testability problem based on two simple properties that characterize locally testable automata.>

We present a tool that is useful in the design and analysis of systolic systems. Specifically, we give characterizations of systolic arrays in terms of (single processor) sequential machines which are easier to program and to analyze. We give several examples to illustrate the utility of the design tool. In particular, we show how systolic designs for such problems as integer bitwise multiplication, dynamic programming, and language recognition can easily be derived using the characterizations. We also present some new results concerning the properties and computational power of systolic arrays which can be obtained using the characterizations.

We look at a simple, but general model, of a systolic system called a trellis automaton (TA). A TA is equivalent in computational power to a one-dimensional unbounded cellular automaton (CA), a model of parallel computation which has been studied extensively in the literature. Different varieties of TA’s are equivalent to corresponding variations of CA’s. We present, for the first time, sequential machine characterizations of TA’s (CA’s). The sequential machines are useful and powerful tools for investigating properties of TA’s (CA’s). They ar easy to program because, unlike the parallel models, one does not have to deal with the problem of synchronization. Several applications are given. In particular, we prove a new speed-up theorem which is stronger than what has previously been shown.

We offer a methodology for simplifying the design and analysis of systolic systems. Specifically, we give characterization of systolic arrays in terms of (single processor) sequential machines which are easier to analyze and to program. We give several examples to illustrate the design methodology. In particular, we show how systolic arrays can be easily designed to implement priority queues, integer bitwise multiplication, dynamic programming, etc. Because the designs are based on the sequential machine, the constructions we obtain are much simpler then those that have appeared in the literature. We also give some results concerning the properties and computational power (e.g., speed-up, hierarchy, etc.) of systolic arrays.