Narrow Results

The aim of this paper is to compare three efficient representations of the position automaton of a regular expression: the Thompson ∊-automaton, the -structure and the ℱ-structure, an optimization of the -structure. These representations are linear w.r.t. the size s of the expression, since their construction is in O(s) space and time, as well as the computation of the set δ(X,a) of the targets of the transitions by a of any subset X of states. The comparison is based on the evaluation of the number of edges of the underlying graphs respectively created by the construction step or visited by the computation of a set δ(X,a).

We discuss the power and limitation of various "advice," when it is given particularly to weak computational models of one-tape linear-time Turing machines and one-way finite (state) automata. Of various advice types, we consider deterministically-chosen advice (not necessarily algorithmically determined) and randomly-chosen advice (according to certain probability distributions). In particular, we show that certain weak machines can be significantly enhanced in computational power when randomized advice is provided in place of deterministic advice.

We continue the investigation of union-free regular languages that are described by regular expressions without the union operation. We also define deterministic union-free languages as languages accepted by one-cycle-free-path deterministic finite automata, and show that they are properly included in the class of union-free languages. We prove that (deterministic) union-freeness of languages does not accelerate regular operations, except for the reversal in the nondeterministic case.

It is known that an ordinal is the order type of the lexicographic ordering of a regular language if and only if it is less than ω^ω. We design a polynomial time algorithm that constructs, for each well-ordered regular language L with respect to the lexicographic ordering, given by a deterministic finite automaton, the Cantor Normal Form of its order type. It follows that there is a polynomial time algorithm to decide whether two deterministic finite automata accepting well-ordered regular languages accept isomorphic languages. We also give estimates on the state complexity of the smallest "ordinal automaton" representing an ordinal less than ω^ω, together with an algorithm that translates each such ordinal to an automaton.

Sequences (L_n | n ≥ k), called streams, of regular languages L_n are considered, where k is some small positive integer, n is the state complexity of L_n, and the languages in a stream differ only in the parameter n, but otherwise, have the same properties. The following measures of complexity are proposed for any stream: (1) the state complexity n of L_n, that is, the number of left quotients of L_n (used as a reference); (2) the state complexities of the left quotients of L_n; (3) the number of atoms of L_n; (4) the state complexities of the atoms of L_n; (5) the size of the syntactic semigroup of L_n; and the state complexities of the following operations: (6) the reverse of L_n; (7) the star of L_n; (8) union, intersection, difference and symmetric difference of L_m and L_n; and (9) the concatenation of L_m and L_n. A stream that has the highest possible complexity with respect to these measures is then viewed as a most complex stream. The language stream (U_n(a, b, c) | n ≥ 3) is defined by the deterministic finite automaton with state set {0, 1, … , n−1}, initial state 0, set {n−1} of final states, and input alphabet {a, b, c}, where a performs a cyclic permutation of the n states, b transposes states 0 and 1, and c maps state n − 1 to state 0. This stream achieves the highest possible complexities with the exception of boolean operations where m = n. In the latter case, one can use U_n(a, b, c) and U_n(b, a, c), where the roles of a and b are interchanged in the second language. In this sense, U_n(a, b, c) is a universal witness. This witness and its extensions also apply to a large number of combined regular operations.

The quotient complexity of a regular language L, which is the same as its state complexity, is the number of left quotients of L. An atom of a non-empty regular language L with n quotients is a non-empty intersection of the n quotients, which can be uncomplemented or complemented. An NFA is atomic if the right language of every state is a union of atoms. We characterize all reduced atomic NFAs of a given language, i.e., those NFAs that have no equivalent states. We prove that, for any language L with quotient complexity n, the quotient complexity of any atom of L with r complemented quotients has an upper bound of 2ⁿ − 1 if r = 0 or r = n; for 1 ≤ r ≤ n − 1 the bound is

The syntactic complexity of a subclass of the class of regular languages is the maximal cardinality of syntactic semigroups of languages in that class, taken as a function of the state complexity n of these languages. We prove that n! and ⌊e(n − 1)⌋. are tight upper bounds for the syntactic complexity of ℛ- and 𝒥-trivial regular languages, respectively.

We continue our study of the class of Fibonacci-automatic words. These are infinite words whose nth term is defined in terms of a finite-state function of the Fibonacci representation of n. In this paper, we show how enumeration questions (such as counting the number of squares of length n in the Fibonacci word) can be decided purely mechanically, using a decision procedure. We reprove some known results, in a unified way, using our technique, and we prove some new results. We also examine abelian properties of these words. As a consequence of our results on abelian properties, we get the result that every nontrivial morphic image of the Fibonacci word is Fibonacci-automatic.

We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural number $>25$ is the sum of at most three natural numbers whose base-$2$ representation has an equal number of $0$’s and $1$’s.

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.

In this paper, we will introduce a new subclass of bitone sequential decision process (bsdp) and give a representation theorem for the subclass called positively/negatively bsdp, shortly, p/n bsdp, that is, necessary and sufficient condition for p/n bsdp to strongly represent a given discrete decision process (ddp).

This paper considers extended finite automata over monoids, in the sense of Dassow and Mitrana. We show that the family of languages accepted by extended finite automata over a monoid K is controlled by the word problem of K in a precisely stated manner. We also point out a critical error in the proof of the main result in the paper by Dassow and Mitrana. However as one consequence of our approach, by analyzing a certain word problem, we obtain a complete proof of this result, namely that the family of languages accepted by extended finite automata over the free group of rank two is exactly the family of context-free languages. We further deduce that along with the free group of rank two, the only finitely generated groups with this property are precisely the groups that have a nonabelian free subgroup of finite index.

In this paper, we study the complexity of deciding code and monoid properties for regular sets specified by deterministic or nondeterministic finite automata. The results are as follows. The code problem for regular sets specified by deterministic or nondeterministic finite automata is NL-complete under NC⁽¹⁾ reducibilities. The problems of determining whether a regular set given by a deterministic finite automaton is a monoid or a free monoid or a finitely generated monoid are all NL-complete under NC⁽¹⁾ reducibilities. These monoid problems become PSPACE-complete if the regular sets are specified by nondeterministic finite automata instead. The maximal code problem for deterministic finite automata is shown to be in DET and NL-hard, while a PSPACE upper bound and NP-hardness lower bound hold for the case of nondeterministic finite automata.

We propose a general approach to compute the seed sensitivity, that can be applied to different definitions of seeds. It treats separately three components of the seed sensitivity problem — a set of target alignments, an associated probability distribution, and a seed model — that are specified by distinct finite automata. The approach is then applied to a new concept of subset seeds for which we propose an efficient automaton construction. Experimental results confirm that sensitive subset seeds can be efficiently designed using our approach, and can then be used in similarity search producing better results than ordinary spaced seeds.

The paper presents a contribution to minimization of fuzzy automata. Traditionally, the problem of minimization of fuzzy automata results directly from the problem of minimization of ordinary automata. That is, given a fuzzy automaton, describe an automaton with the minimal number of states which recognizes the same language as the given one. In this paper, we formulate a different problem. Namely, the minimal fuzzy automaton we are looking for is required to recognize a language which is similar to the language of the given fuzzy automaton to a certain degree a, such as a = 0.9, prescribed by a user. That is, we relax the condition of being equal to a weaker condition of being similar to degree a.

In this paper we consider dynamic processes, in repeated games, that are subject to the natural informational restriction of uncoupledness. We study the almost sure convergence of play (the period-by-period behavior as well as the long-run frequency) to Nash equilibria of the one-shot stage game, and present a number of possibility and impossibility results. Basically, we show that if in addition to random experimentation some recall, or memory, is introduced, then successful search procedures that are uncoupled can be devised. In particular, to get almost sure convergence to pure Nash equilibria when these exist, it suffices to recall the last two periods of play.