Approximate computation is a central concept in algorithms and computation theory. Our notion of approximation is that the algorithm performs correctly on most of the inputs. We propose some finite automata models to study the question of how well a finite automaton can approximately recognize a non-regular language. On the one hand, we show that there are natural problems for which a DFA can correctly solve almost all the instances, but not all instances. An example of such a problem is a decision question about the number of digits in the square of a given integer. On the other hand, we show that some languages (such as L majority = {x ∈ (0 + 1)* | x has more 1′s than 0′s }) can't be approximated by any regular language in a strong sense. We also show that there are problems that are intermediate (between the extremes stated above) in terms of how we well a regular language can approximate it. An example of such a problem is a decision question about the number of digits in the product of two integers. We also present results comparing different models of approximation.

Finite automata (FA’s) are of fundamental importance in theory and in applications. The following basic minimization problem is studied: Given a DFA (deterministic FA), find a minimum equivalent nondeterministic FA (NFA). This paper shows that the natural decision problem associated with it is PSPACE-complete. More generally, let ${\text{A}} \to {\text{B}}$ denote the problem of converting a given FA of type A to a minimum FA of type B. This paper also shows that most of these problems are computationally hard. Motivated by the question of how much nondeterminism suffices to make the decision problem involving an NFA computationally hard, the authors study the complexity decision problems for FA’s and present several intractability results, even for cases in which the input is deterministic or nondeterministic with a very limited nondeterminism. For example, it is shown that it is PSPACE-complete to decide if $L(M_1 ) \cdot L(M_2 ) = L(M_3 )$, where $M_1 $, $M_2 $, and $M_3 $ are DFAs. These problems are related to some classical problems in automata theory (such as deciding whether an FA has the finite power property), as well as recent ones (such as determining the diversity of a given FA).

The authors study the problem of sorting n distinct elements in ascending sequence according to a total order, using comparison queries which receive 'yes' or 'no' answers, but of which as many as e may be erroneous. In a half-lie version, all 'yes' answers are guaranteed to be correct and the errors are confined to 'no' answers. It is shown that the comparison query complexity of the sorting problem for this case is Omega (n log n+e), and an asymptotically optimal algorithm is demonstrated. In a full-lie version, both 'yes' and 'no' answers can be false. It is shown that the comparison query complexity of the sorting problem for this case is Omega (n log n+en).>

This paper considers the problem of how the size of a nondeterministic finite automaton (nfa) representing a regular language depends on the type of ambiguity of the nfa. Primarily, the relationship between the ambiguity and the size in five types of nfa’s with increasing degrees of nondeterminism is studied: DFA (deterministic), ${\operatorname{UNA}}$ (unambiguous), ${\operatorname{FNA}}$ (finitely ambiguous), ${\operatorname{PNA}}$ (polynomially ambiguous), and ${\operatorname{ENA}}$ (exponentially ambiguous) nfa’s. The goal is to show “separation” among these classes, where a class A is said to be “separated” from B (written ($A,B$)) if for infinitely many n, there are machines of type B with n states whose minimal equivalent type A machine has more than $p(n)$ states for any polynomial p. Two classes are “polynomially equivalent” (written $A = B$) if machines of type A can be converted to machines of type B with only a polynomial increase in the number of states, and vice versa. For a class X, let $X(b)$) denote the restricted class of machines of type X with the restriction that the language accepted is bounded. The first main result compares the bounded restrictions of the five classes mentioned above. Specifically, the following is shown: $({\operatorname{DFA}}(b),{\operatorname{UNA}}(b)),({\operatorname{UNA}}(b),{\operatorname{FNA}}(b)),{\operatorname{FNA}}(b) = {\operatorname{PNA}}(b)$ and ${\operatorname{PNA}}(b) = {\operatorname{ENA}}(b)$, providing a complete picture of how the type of ambiguity affects the size complexity for unary and bounded languages. For unbounded languages it is conjectured that each of the five types of nondeterminism is separate from its higher types. But a proof does not exist at this time for two of the separations, the other two carrying over directly from the unary case. Candidates are offered that may be useful in proving the (other two) conjectured separations, and also a weaker form of separation in one case is shown. The notion of “concurrent conciseness” introduced by Kintala and Wotschke is studied. A class C is said to be concurrently concise over two classes A and B if $(A,B)$ and $(B,C)$ can be proved using the same collection of witness languages. One of the main results of this paper shows that, for unrestricted inputs, PNA is concurrently concise over ${\operatorname{DFA}}$ and ${\operatorname{UNA}}$. This answers an open problem of Stearns and Hunt. The succinctness problem is also studied through (regularity preserving) closure properties, an approach initiated by Sakoda and Sipser, and some interesting contrasts between various classes of nfa’s are shown.