Narrow Results

In this paper, we study the tradeoffs in descriptional complexity of NFA (nondeterministic finite automata) of various amounts of ambiguity. We say that two classes of NFA are separated if one class can be exponentially more succinct in descriptional sizes than the other. New results are given for separating DFA (deterministic finite automata) from UFA (unambiguous finite automata), UFA from MDFA (DFA with multiple initial states) and UFA from FNA (finitely ambiguous NFA). We present a family of regular languages that we conjecture to be a good candidate for separating FNA from LNA (linearly ambiguous NFA).

Iwama et al. showed that there exists an n-state binary nondeterministic finite automaton such that its equivalent minimal deterministic finite automaton has exactly 2ⁿ - α states, for all n ≥ 7 and 5 ≤ α ≤ 2n-2, subject to certain coprimality conditions. We investigate the same question for both unary and binary symmetric difference nondeterministic finite automata. In the binary case, we show that for any n ≥ 4, there is an n-state symmetric difference nondeterministic finite automaton for which the equivalent minimal deterministic finite automaton has 2^{n - 1} + 2^{k - 1} - 1 states, for 2 < k ≤ n - 1. In the unary case, we consider a large practical subclass of unary symmetric difference nondeterministic finite automata: for all n ≥ 2, we argue that there are many values of α such that there is no n-state unary symmetric difference nondeterministic finite automaton with an equivalent minimal deterministic finite automaton with 2ⁿ - α states, where 0 < α < 2^{n - 1}. For each n ≥ 2, we quantify such values of α precisely.

The question whether nondeterminism is more powerful than determinism for two-way automata is one of the most famous old open problems on the border between formal language theory and automata theory. An exponential gap between the number of states of two-way nondeterministic finite automata (2NFA) and their deterministic counterparts (2DFA) was proved only for some restricted versions of two-way automata up to now. This problem is also related to the famous DLOG vs. NLOG problem. A superpolynomial gap between 2NFAs and 2DFAs on words of polynomial length in the parameter of a complete language of Sipser and Sakoda for the 2DFA vs. 2NFAs problem would imply that DLOG is a proper subset of NLOG.

The first goal of this paper is first to survey the attempts to solve the 2DFA vs. 2NFA problem. After that we discus why this problem is so hard in spite of the fact that one has a very clear intuition why nondeterminism has to be more powerful than determinism for this computing model. It seems that the hardness lies in the fact that, when trying to prove lower bounds on the number of states of 2DFAs, we are not able to force the states to have a clear meaning. When designing an automaton, we always assign an unambiguous interpretation to each state. In an attempt to capture the concept of meaning of states we introduce a new restriction on the two-way automata: Each state is assigned a logical formula expressing some properties of the input word, and transitions of the automaton must be designed in such a way that the assigned formula is true whenever the automaton is in the given state. In our approach we use propositional formulæ with various interpreted atoms. For two possible logics we prove an exponential gap between 2NFAs and 2DFAs. Moreover, using our concept of assigning meaning to the states of 2DFAs we show that there is no exponential gap between general 2NFAs and 2DFAs on inputs of a polynomial length of the complete language of Sakoda and Sipser.

We introduce planar directed acyclic graph algebras and present an explicit minimization method. The minimal simulation of a nondeterministic automaton on planar directed acyclic graphs is constructed.

The language consists of first halfs of strings in L. Many other variants of a proportional removal operation have been considered in the literature and a characterization of removal operations that preserve regularity is known. We consider the nondeterministic state complexity of the operation and, more generally, of polynomial removals as defined by Domaratzki (J. Automata, Languages and Combinatorics 7(4), 2002). We give an O(n²) upper bound for the nondeterministic state complexity of polynomial removals and a matching lower bound in cases where the polynomial is a sum of a monomial and a constant, or when the polynomial has rational roots.

We present several new results on minimal space requirements to recognize a nonregular language: (i) realtime nondeterministic Turing machines can recognize a nonregular unary language within weak log log n space, (ii) log log n is a tight space lower bound for accepting general nonregular languages on weak realtime pushdown automata, (iii) there exist unary nonregular languages accepted by realtime alternating one-counter automata within weak log n space, (iv) there exist nonregular languages accepted by two-way deterministic pushdown automata within strong log log n space, and, (v) there exist unary nonregular languages accepted by two-way one-counter automata using quantum and classical states with middle log n space and bounded error.

Let 2N be the class of families of problems solvable by families of two-way nondeterministic finite automata of polynomial size. We characterize 2N in terms of families of formulas of transitive-closure logic. These formulas apply the transitive-closure operator on a quantifier-free disjunctive normal form of first-order logic with successor and constants, where (i) apart from two special variables, all others are equated to constants in every clause, and (ii) no clause simultaneously relates these two special variables and refers to fixed input cells. We prove that automata with polynomially many states are as powerful as formulas with polynomially many clauses and polynomially large constants. This can be seen as a refinement of Immerman’s theorem that nondeterministic logarithmic space matches positive transitive-closure logic ($\mathrm{\text{NL}}=\mathrm{\text{FO}}+\mathrm{\text{posTC}}$).

It is one of the most famous open problems to determine the minimum amount of states required by a deterministic finite automaton to distinguish a pair of strings, which was stated by Christian Choffrut more than thirty years ago.

We investigate the same question for different automata models and we obtain new upper and lower bounds for some of them including alternating, ultrametric, quantum, and affine finite automata.

Many nondeterminism measures for finite automata have been studied in the literature. The tree width of an NFA (nondeterministic finite automaton) counts the number of leaves of computation trees as a function of input length. The trace of an NFA is defined in terms of the largest product of the degrees of nondeterministic choices in computations on inputs of given length. Branching is the corresponding best case measure based on the product of nondeterministic choices in the computation that minimizes this value. We establish upper and lower bounds for the trace of an NFA in terms of its tree width. We give a tight bound for the size blow-up of determinizing an NFA with finite trace. Also we show that the trace of any NFA either is bounded by a constant or grows exponentially.

To get a more comprehensive understanding of the amount of branching in computations of a nondeterministic finite automaton (NFA), we introduce and study the string path width and depth path width measures. For a given NFA, the string path width on a string $w$ counts the number of all complete computations on $w$, and the depth path width on an integer $\ell$ counts the number of complete computations on all strings of length $\ell$. We give an algorithm to decide the finiteness of the depth path width of an NFA. Deciding finiteness of string path width can be reduced to the corresponding question on ambiguity.

An NFA is nearly acyclic if any computation can pass through at most one cycle. The class of nearly acyclic NFAs consists of exactly all NFAs with finite depth path width. Using this characterization we show that the finite depth path width of an $m$-state NFA over a $k$-letter alphabet is at most ${(k+1)}^{m-1}$ and that this bound is tight. The nearly acyclic NFAs recognize exactly the class of constant density regular languages.

Many difficult open problems in theoretical computer science center around non-determinism. We study the fundamental problem of converting a given deterministic finite automaton (DFA) to a minimal nondeterministic finite automaton (NFA). Despite extensive work on finite automata, this fundamental problem has remained open. Recently, we studied this problem and showed that this (and related) problems are computationally hard.¹¹ Herewe study the restriction of this problem to the case when the input DFA is over a one-letter alphabet. Even in this restricted case the problem is computationally hard even though our evidence of hardness is different from (and is weaker than) the standard ones such as NP-hardness. Let A→B denote the problem of converting a finite automaton of type A to a minimal finite automaton of type B. Our main result is that DFA→NFA, when the input is a unary cyclic DFA (a DFA whose graph is a simple cycle), is in NP but not in P unless NP⊆DTIME (n^{O(log n)}). Our work was also motivated by the problem of finding structurally simple “normal forms” of NFA’s over a unary alphabet. We present some normal forms for minimal NFA’s over a unary alphabet and present an application to lower bounds on the size complexity of an NFA. In fact, the normal form result is used in a nontrivial manner to show the NP membership result stated above.

Interconnecting computers into clusters or computational grids promises many benefits for users of computational science and engineering, especially in terms of performance and costs. This situation is additionally supported by programming libraries like MPI and PVM, which are portable across different platforms and allow to exploit the available computing power. Consequently, the number of applications utilizing these computing structures is steadily increasing. Yet, there are also some pitfalls with possibly serious consequences, that must not be ignored by software developers. This paper describes some critical issues related to nondeterministic program behavior. With such kinds of programs different program executions are observed although the same input data are provided, leading to the irreproducibility effect, the completeness problem, and the probe effect. The impact of these effects, their weight for software developers, and how they are affected on supercomputer architectures and cluster environments are discussed. These critical issues need to be pointed out to users in order to raise their understanding and awareness of the problems. While the irreproducibility effect is believed to be sufficiently solved by record&replay mechanisms, existing solutions for the probe effect are only partially successful, and only very few approaches address the completeness problem. A simple solution for the latter is offered by automatic event manipulation and artificial replay, which is however restricted by time and memory constraints. In addition, this solution to the completeness problem also solves the probe effect in nondeterministic parallel programs.

The idea of nondeterministic typical hesitant fuzzy automata is a generalization of the fuzzy automata presented by Costa and Bedregal. This paper, presents the sufficient and necessary conditions for a typical hesitant fuzzy language to be computed by nondeterministic typical hesitant fuzzy automata. Besides, the paper introduces a new class of typical hesitant fuzzy automata with crisp transitions, and we will show that this new class is equivalent to the original class introduced by Costa and Bedregal.

We present a mathematical framework (referred to as Context-driven Actualization of Potential, or CAP) for describing how entities change over time under the influence of a context. The approach facilitates comparison of change of state of entities studied in different disciplines. Processes are seen to differ according to the degree of nondeterminism, and the degree to which they are sensitive to, internalize, and depend upon a particular context. Our analysis suggests that the dynamical evolution of a quantum entity described by the Schrödinger equation is not fundamentally different from change provoked by a measurement often referred to as collapse but a limiting case, with only one way to collapse. The biological transition to coded replication is seen as a means of preserving structure in the face of context, and sexual replication as a means of increasing potentiality thus enhancing diversity through interaction with context. The framework sheds light on concepts like selection and fitness, reveals how exceptional Darwinian evolution is as a means of 'change of state', and clarifies in what sense culture (and the creative process underlying it) are Darwinian.