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.>

Since about 1971, much research has been done on Thue systems that have properties that ensure viable and efficient computation. The strongest of these is the Church-Rosser property, which states that two equivalent strings can each be brought to a unique canonical form by a sequence of length-reducing rules. In this paper three ways in which formal languages can be defined by Thue systems with this property are studied, and some general results about the three families of languages so determined are studied.

In [1] various problems are solved about the possibility of mapping regular sets into or onto other regular sets by means of a complete sequential machine or a generalized sequential machine under various restraints. One problem in this class has remained open. That problem, as restated on pp. 129-130 of [2], is whether it is “recursively solvable to determine for arbitrary regular sets L1 and L2 whether there exists a generalized sequential machine S such that S(L1) = L2.” The claim is hereby made on the affirmative solution to this problem.

A decision procedure is given which determines whether the languages defined by two parenthesis grammars are equal.

This paper contains some applications of an elementary study of unate truth functions. One application is a method of deciding when a truth function is linearly separated, i. e., is expressible as a linear polynomial inequality in its arguments (letting 1 represent truth and 0 represent falsity). Other applications are to contact nets and to rectifier nets. Much of the material of this paper, although not in print, is well known to some logicians and switching theorists. Nothing from the first three sections is original.

Algorithms are presented for 1) converting a state graph describing the behavior of an automaton to a regular expression describing the behavior of the same automaton (section 2), and 2) for converting a regular expression into a state graph (sections 3 and 4). These algorithms are justified by theorems, and examples are given. The first section contains a brief introduction to state graphs and the regular-expression language.

These systems are roughly natural number theory in, respectively, nth order function calculus, for all positive integers n. Each of these systems is expressed in the notation of the theory of types, having variables with type subscripts from 1 to n. Variables of type 1 stand for natural numbers, variables of type 2 stand for classes of natural numbers, etc. Primitive atomic wff's (well-formed formulas) of Tn are those of number theory in variables of type 1, and of the following kind for n > 1: xi ϵ yi+1. Other wff's are formed by truth functions and quantifiers in the usual manner. Quantification theory holds for all the variables of Tn. Tn has the axioms Z1 to Z9, which are, respectively, the nine axioms and axiom schemata for the system Z (natural number theory) on p. 371 of [1]. These axioms and axiom schemata contain only variables of type 1, except for the schemata Z2 and Z9, which are as follows: where ‘F(x1)’ can be any wff of Tn. Identity is primitive for variables of type 1; for variables of other types it is defined as follows:

In this paper we shall use a logic with truth values ranging over all the real numbers x such that 0 ≦ x ≦ 1.1 will be “complete truth” and 0 will be “complete falsity.” The primitive sentential connectives are ‘⊃’ and ‘∼’; other connectives are ‘∨’ and ‘·’. Assume that ‘p’ and ‘q’ are sentential variables, whose truth values are respectively x and y. Then 1.1. ‘p ⊃ q’ has the value min(1 − x + y, 1), 1.2. ‘∼p’ has the value 1 − x, 1.3. ‘p∨q’ has the value max(x, y), and 1.4. ‘p·q’ has the value min (x, y). ‘∨’ and ‘·’ can be defined as follows: It is the purpose of this paper to prove a theorem which will be stated in the next section. The following symbolism and convention will be used throughout the paper: S is a logical formula. ν (S) is the value of S. ‘p’, ‘pi1, ’p2, …, ‘q’, are sentential variables. ν(p) = x and ν(x1) = x1, etc. ν(S) = σ and ν(S1) = σ1, etc. If S contains the sentential variables ‘p1’, ‘p2’, …, then we write for S, S(p1, P2, …). Also ν{S(p1, p2, …)) = σ(x1, x2, …). A logical formula is defined in the usual manner. 1. A sentential variable is a logical formula; 2. if S is a logical formula then ·S is a logical formula; and 3. if S and S′ are logical formulae then (S ⊃ S′) is a logical formula.