International Journal of Foundations of Computer Science

Professor Sheng Yu passed away on January 23, 2012, the first day of the Lunar New Year, the Year of the Dragon. He was only sixty-one years old. His death was a tremendous loss to his family, friends, colleagues, co-workers, co-authors, co-editors, members of conference program committees, students, the theoretical Computer Science Community and especially to his beloved wife, Lizhen. Through his teachings, international committee work, seminars and some 150 refereed publications, he left us a huge legacy of many interesting and important research contributions in the areas of the theory and implementation of automata and formal languages, fuzzy logic, object-oriented modeling methodologies, parallel processing for parallel programming languages, important software projects for automata theory research, the creation of the international Conference on Implementation and Application of Automata (CIAA) and a gallery of vivid memories of the wonderful times shared. He is remembered for his enormous energy, competence, diligence, anticipatory thoughtfulness, over-the-top generosity, measured politeness, noble sportsmanship and committed friendship. This paper, an extension of a talk with a similar title at DLT 2012, is an account how we are commemorating Sheng.

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.

Recovering unknown inputs in oracles with as few queries as possible is one of the most basic problems in theoretical computer science. In this paper, we survey the classical and quantum query complexity of this problem for various types of oracles with different types of queries.

In this paper we provide a summary on important results concerning P automata and their distributed systems, dP automata. Since these constructs combine properties of classical automata and membrane systems being in interaction with their environments, we also discuss their non-standard features, compared them to characteristics of classical automata.

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

It is known that if a Büchi context-free language (BCFL) consists of scattered words, then there is an integer n, depending only on the language, such that the Hausdorff rank of each word in the language is bounded by n. Every BCFL is a Muller context-free language (MCFL). In the first part of the paper, we prove that an MCFL of scattered words is a BCFL iff the rank of every word in the language is bounded by an integer depending only on the language.

Then we establish operational characterizations of the BCFLs of well-ordered and scattered words. We prove that a language is a BCFL consisting of well-ordered words iff it can be generated from the singleton languages containing the letters of the alphabet by substitution into ordinary context-free languages and the ⍵-power operation. We also establish a corresponding result for BCFLs of scattered words and define expressions denoting BCFLs of well-ordered and scattered words. In the final part of the paper we give some applications.

The paper characterizes the family of homomorphisms, under which the deterministic context-free languages, the LL context-free languages and the unambiguous context-free languages are closed. The family of deterministic context-free languages is closed under a homomorphism h if and only if h is either a code of bounded deciphering delay, or the images of all symbols under h are powers of the same string. The same characterization holds for LL context-free languages. The unambiguous context-free languages are closed under h if and only if either h is a code, or the images of all symbols under h are powers of the same string.

The edit-distance between two strings is the smallest number of operations required to transform one string into the other. The distance between languages L₁ and L₂ is the smallest edit-distance between string w_i ∈ L_i, i = 1, 2. We consider the problem of computing the edit-distance of a given regular language and a given context-free language. First, we present an algorithm that finds for the languages an optimal alignment, that is, a sequence of edit operations that transforms a string in one language to a string in the other. The length of the optimal alignment, in the worst case, is exponential in the size of the given grammar and finite automaton. Then, we investigate the problem of computing only the edit-distance of the languages without explicitly producing an optimal alignment. We design a polynomial time algorithm that calculates the edit-distance based on unary homomorphisms.

We introduce E-equivalence, which is a straightforward generalization of almost-equivalence. While almost-equivalence asks for ordinary equivalence up to a finite number of exceptions, in E-equivalence these exceptions or errors must belong to a (regular) set E. The computational complexity of deterministic finite automata (DFAs) minimization problems and their variants w.r.t. almost- and E-equivalence are studied. We show that there is a significant difference in the complexity of problems related to almost-equivalence, and those related to E-equivalence. Moreover, since hyper-minimal and E-minimal automata are not necessarily unique (up to isomorphism as for minimal DFAs), we consider the problem of counting the number of these minimal automata.

The class of languages captured by Constrained Automata (CA) that are unambiguous is shown to possess more closure properties than the provably weaker class captured by deterministic CA. Problems decidable for deterministic CA are nonetheless shown to remain decidable for unambiguous CA, and testing for regularity is added to this set of decidable problems. Unambiguous CA are then shown incomparable with deterministic reversal-bounded machines in terms of expressivity, and a deterministic model equivalent to unambiguous CA is identified.

We study different possibilities of combining the concept of homomorphic replacement with regular expressions in order to investigate the class of languages given by extended regular expressions with backreferences (REGEX). It is shown in which regard existing and natural ways to do this fail to reach the expressive power of REGEX. Furthermore, the complexity of the membership problem for REGEX with a bounded number of backreferences is considered.

Two words u and v are k-abelian equivalent if they contain the same number of occurrences of each factor of length at most k. This leads to a hierarchy of equivalence relations on words which lie properly in between the equality and abelian equality. The goal of this paper is to analyze Fine and Wilf's periodicity theorem with respect to these equivalence relations. Fine and Wilf's theorem tells exactly how long a word with two periods p and q can be without having the greatest common divisor of p and q as a period. Recently, the same question has been studied for abelian periods. In this paper we show that for k-abelian periods the situation is similar to the abelian case: In general, there is no bound for the lengths of such words, but the values of the parameters p, q and k for which the length is bounded can be characterized. In the latter case we provide nontrivial upper and lower bounds for the maximal lengths of such words. In some cases (e.g., for k = 2) we found the maximal length precisely.

We consider words over an arbitrary alphabet admitting multiple pseudoperiods according to permutations. We describe the conditions under which such a word exists. Moreover, a natural generalization of Fine and Wilf's Theorem is proved. Finally, we introduce and describe a new family of words sharing properties with the so-called central words. In particular, under some simple conditions, we prove that these words are pseudopalindromes, a result consistent with the fact that central words are palindromes.

We shall show that (i) there exists a binary NP-complete language such that its unary coded version is in ASPACE(log log n), (ii) if P ≠ NP, there exists a binary language such that its unary version is in ASPACE(log log n), while the language itself is not in ASPACE(log n). As a consequence, under assumption that P ≠ NP, the standard space translation between unary and binary languages does not work for alternating machines with small space; the equivalence is valid only if s(n) ∈ Ω(n). This is quite different from deterministic and nondeterministic machines, for which the corresponding equivalence holds for each s(n) ∈ Ω(log n), and hence for s(log n) ∈ Ω(log log n). Under assumption that NP ≠ co-NP, we also show that binary versions of unary languages in ASPACE(log log n) form a complexity class not contained in NP.