International Journal of Foundations of Computer Science

In this paper, the relation between the Glushkov automaton and the partial derivative automaton of a given regular expression, in terms of transition complexity, is studied. The average transition complexity of was proved by Nicaud to be linear in the size of the corresponding expression. This result was obtained using an upper bound of the number of transitions of . Here we present a new quadratic construction of that leads to a more elegant and straightforward implementation, and that allows the exact counting of the number of transitions. Based on that, a better estimation of the average size is presented. Asymptotically, and as the alphabet size grows, the number of transitions per state is on average 2. Broda et al. computed an upper bound for the ratio of the number of states of to the number of states of which is about ½ for large alphabet sizes. Here we show how to obtain an upper bound for the number of transitions in , which we then use to get an average case approximation. In conclusion, assymptotically, and for large alphabets, the size of is half the size of the . This is corroborated by some experiments, even for small alphabets and small regular expressions.

Infinite games are studied in a format where two players, called Player 1 and Player 2, generate a play by building up an ω-word as they choose letters in turn. A game is specified by the ω-language which contains the plays won by Player 2. We analyze ω-languages generated from certain classes of regular languages of finite words (called *-languages), using natural transformations of *-languages into ω-languages. Winning strategies for infinite games can be represented again in terms of *-languages. Continuing work of Selivanov (2007) and Rabinovich et al. (2007), we analyze how these "strategy *-languages" are related to the original language class . In contrast to that work, we exhibit classes where strategy representations strictly exceed .

Non-Archimedean words have been introduced as a new type of infinite words which can be investigated through classical methods in combinatorics on words due to a length function. The length function, however, takes values in the additive group of polynomials ℤ[t] (and not, as traditionally, in ℕ), which yields various new properties. Non-Archimedean words allow to solve a number of interesting algorithmic problems in geometric and algorithmic group theory. There is also a connection to logic and the first-order theory in free groups (Tarski Problems).

In the present paper we provide a general method to use infinite words over a discretely ordered abelian group as a tool to investigate certain group extensions for an arbitrary group G. The central object is a group E(A, G) which is defined in terms of a non-terminating, but confluent rewriting system. The groupG as well as some natural HNN-extensions of G embed into E(A, G) (and still "behave like" G), which makes it interesting to study its algorithmic properties. In order to show that every group G embeds into E(A, G) we combine methods from combinatorics on words, string rewriting and group theory.

We investigate Abelian primitive words, which are words that are not Abelian powers. We show the set of Abelian primitive words is not context-free. We can determine whether a word is Abelian primitive in linear time (for fixed alphabet size). Also differently from classical primitive words, we find that a word may have more than one Abelian root. We also consider enumeration of Abelian primitive words.

We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give some new characterizations of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems.

We focus on Θ-rich and almost Θ-rich words over a finite alphabet , where Θ is an involutive antimorphism over . We show that any recurrent almost Θ-rich word u is an image of a recurrent Θ′-rich word under a suitable morphism, where Θ′ is also an involutive antimorphism. Moreover, if the word u is uniformly recurrent, we show that Θ′ can be set to the reversal mapping. We also treat one special case of almost Θ-rich words: we show that every Θ-standard word with seed is an image of an Arnoux-Rauzy word.

We discuss a number of essential questions concerning the state complexity research. The questions include why many basic problems were not studied earlier, whether there is a general algorithm for state complexity of combined operations, and whether there is a new and effective approach in this area of research. The concept of state complexity approximation is also discussed. We show that state complexity approximation can be used to obtain good results when the exact state complexities are difficult to find and when the exact state complexities are too complex to comprehend. We also list a number of questions for future research in this area.

The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirmative answer to this question, by demonstrating a non-context-free language that can be recognized with perfect soundness by a rtQ1CA. This is the first demonstration of the superiority of a quantum model to the corresponding classical one in the real-time case with an error bound less than 1. We also introduce a generalization of the rtQ1CA, the quantum one-way one-counter automaton (1Q1CA), and show that they too are superior to the corresponding family of probabilistic machines. For this purpose, we provide general definitions of these models that reflect the modern approach to the definition of quantum finite automata, and point out some problems with previous results. We identify several remaining open problems.

Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous, and it was shown that 2QCFA have superiority over two-way probabilistic finite automata (2PFA) for recognizing some non-regular languages such as the language L_eq = {aⁿbⁿ ∣ n ∈ N} and the palindrome language L_pal = {w ∈ {a,b}* ∣ w=w^R}, where x^R is x in the reverse order. It is interesting to find more languages like these that witness the superiority of 2QCFA over 2PFA. In this paper, we consider the language L_m = {xcy ∣ ∑ = {a,b,c},x,y ∈ {a,b}*, ∣x∣ = ∣y∣} that is similar to the middle language L_middle = {xay ∣ x,y ∈ {a,b}*, ∣x∣ = ∣y∣}. We prove that the language L_m show that L_m can be recognized by 2PFA with bounded error, but only in exponential expected time. Thus L_m is another witness of the fact that 2QCFA are more powerful than their classical counterparts.

As was emphasized by Deutsch, quantum computation shatters complexity theory, but is innocuous to computability theory. Yet Nielsen and others have shown how quantum theory as it stands could breach the physical Church-Turing thesis. We draw a clear line as to when this is the case, in a way that is inspired by Gandy. Gandy formulates postulates about physics, such as homogeneity of space and time, bounded density and velocity of information — and proves that the physical Church-Turing thesis is a consequence of these postulates. We provide a quantum version of the theorem. Thus this approach exhibits a formal non-trivial interplay between theoretical physics symmetries and computability assumptions.

The concept of forwarding sets is widely adopted in many broadcast protocols for wireless multihop networks to alleviate the broadcast storm problem. In these protocols, after receiving a broadcast message, each node that is requested to relay the message instructs a subset of its 1-hop neighbors, a.k.a. the forwarding set, to further relay it. In this paper, we propose to use the Minimum Local Disk Cover Set (MLDCS) as the forwarding set in heterogeneous multihop wireless networks, where nodes may have different transmission ranges.We show that the minimum local disk cover set of a node in heterogeneous networks is equivalent to its skyline set, and then we propose a divide-and-conquer algorithm with the optimal time complexity to compute the skyline set locally and statelessly. Moreover, unlike other forwarding heuristics, the proposed algorithm requires only 1-hop neighbor information. This helps to reduce the forwarding set formation latency and thus will be more suitable for environments with a frequently changed network topology, such as vehicular ad hoc networks.

Reaction systems are an abstract model of biochemical reactions in the living cell within a framework of finite (though often large) discrete dynamical systems. In this setting, this paper provides an analytical and experimental study of stability. The notion of stability is defined in terms of the way in which small perturbations to the initial state of a system are likely to change the system's eventual behavior. At the stable end of the spectrum, there is likely to be no change; but at the unstable end, small perturbations take the system into a state that is probabilistically the same as a randomly selected state, similar to chaotic behavior in continuous dynamical systems.