A well known result of Fraenkel and Simpson states that the number of distinct squares in a word of length n is bounded by 2n since at each position there are at most two distinct squares whose last occurrence starts. In this paper, we investigate squares in partial words with one hole,or sequences over a finite alphabet that have a “do not know” symbol or “hole”. A square in a partial word over a given alphabet has the form uv where u is compatible with v, and consequently, such square is compatible with a number of words over the alphabet that are squares. Recently, it was shown that for partial words with one hole, there may be more than two squares that have their last occurrence starting at the same position. Here, we prove that if such is the case, then the length of the shortest square is at most half the length of the third shortest square.As a result, we show that the number of distinct squares compatible with factors of a partial word with one hole of length n is bounded by $\frac{7n}{2}$ .

We prove that for every countable ordinal α one cannot decidewhether a given infinitary rational relation is in the Borel class ${\bf \Sigma_{\alpha}^0}$ (respectively ${\bf \Pi_{\alpha}^0}$ ). Furthermoreone cannotdecide whether a given infinitary rational relation is a Borel set or a ${\bf \Sigma_{1}^1}$ -complete set. We prove some recursive analogues to theseproperties. In particular one cannot decide whether an infinitary rational relation is anarithmetical set.We then deduce from the proof ofthese results some other ones, like: one cannot decide whether thecomplement ofan infinitary rational relation is also an infinitary rational relation.

Circular splicing has been very recently introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we restrict our study to the relationship between regular circular languages and languages generated by finite circular splicing systems and provide some results towards a characterization of the intersection between these two classes. We consider the class of languages X*, called here star languages, which are closed under conjugacy relation and with X being a regular language. Using automata theory and combinatorial techniques on words, we show that for a subclass of star languages the corresponding circular languages are (Paun) circular splicing languages. For example, star languages belong to this subclass when X* is a free monoid or X is a finite set. We also prove that each (Paun) circular splicing language L over a one-letter alphabet has the form L = X+ ∪ Y, with X,Y finite sets satisfying particular hypotheses. Cyclic and weak cyclic languages, which will be introduced in this paper, show that this result does not hold when we increase the size of alphabets, even if we restrict ourselves to regular languages.

In automata theory, quantum computation has been widely examined for finite statemachines, known as quantum finite automata (QFAs), and less attention has been given toQFAs augmented with counters or stacks. In this paper, we focus on such generalizations ofQFAs where the input head operates in one-way or realtime mode, and present some newresults regarding their superiority over their classical counterparts. Our first result isabout the nondeterministic acceptance mode: Each quantum model architecturallyintermediate between realtime finite state automaton and one-way pushdown automaton(one-way finite automaton, realtime and one-way finite automata with one-counter, andrealtime pushdown automaton) is superior to its classical counterpart. The second andthird results are about bounded error language recognition: for anyk > 0, QFAs with k blind counters outperform theirdeterministic counterparts; and, a one-way QFA with a single head recognizes an infinitefamily of languages, which can be recognized by one-way probabilistic finite automata withat least two heads. Lastly, we compare the nondeterminictic and deterministic acceptancemodes for classical finite automata with k blind counter(s), and we showthat for any k > 0, the nondeterministic models outperform thedeterministic ones.

The problem of synchronizing a network of identical processors that work synchronously at discrete steps is studied. Processors are arranged as an array of m rows and n columns and can exchange each other only one bit of information. We give algorithms which synchronize square arrays of (n × n) processors and give some general constructions to synchronize arrays of (m × n) processors. Algorithms are given to synchronize in time n2, $n \lceil \log n\rceil$, $n\lceil\sqrt n \rceil$ and 2n a square array of (n × n) processors. Our approach is a modular description of synchronizing algorithms in terms of "fragments" of cellular automata that are called signals. Compositional rules to obtain new signals (and new synchronization times) starting from known ones are given for an (m × n) array. Using these compositional rules we construct synchronizations in any "feasible" linear time and in any time expressed by a polynomial with nonnegative coefficients.

For polyominoes coded by their boundary word, we describe a quadratic O(n2) algorithm in the boundary length n which improves the naive O(n4) algorithm. Techniques used emanate from algorithmics, discrete geometry and combinatorics on words.

A parallel communicating automata system consists of several automata working independently in parallel and communicating with each other by request with the aim of recognizing a word. Rather surprisingly, returning parallel communicating finite automata systems are equivalent to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata. Some open problems are finally formulated.

In the infinite Post Correspondence Problem an instance (h,g)consists of two morphisms h and g, and the problem is todetermine whether or not there exists an infinite word ωsuch that h(ω) = g(ω). This problem was shown to beundecidable by Ruohonen (1985) in general. Recently Blondel and Canterini (Theory Comput. Syst.36(2003) 231–245) showed that this problem is undecidable for domainalphabets of size 105. Here we give a proof that the infinite PostCorrespondence Problem is undecidable for instances where themorphisms have domains of 9 letters. The proof uses a recentresult of Matiyasevich and Sénizergues and a modification of aresult of Claus.

We discuss some known and introduce some new hierarchies and reducibilities on regular languages, with the emphasis on the quantifier-alternation and difference hierarchies of the quasi-aperiodic languages. The non-collapse of these hierarchies and decidability of some levels are established. Complete sets in the levels of the hierarchies under the polylogtime and some quantifier-free reducibilities are found. Some facts about the corresponding degree structures are established. As an application, we characterize the regular languages whose balanced leaf-language classes are contained in the polynomial hierarchy. For any discussed reducibility we try to give motivations and open questions, in a hope to convince the reader that the study of these reducibilities is interesting for automata theory and computational complexity.

We show that the standard normalization-by-evaluation construction for the simply-typed λβη-calculus has a natural counterpart for the untyped λβ-calculus, with the central type-indexed logical relation replaced by a “recursively defined” invariant relation, in the style of Pitts. In fact, the construction can be seen as generalizing a computational-adequacy argument for an untyped, call-by-name language to normalization instead of evaluation.In the untyped setting, not all terms have normal forms, so the normalization function is necessarily partial. We establish its correctness in the senses of soundness (the output term, if any, is in normal form and β-equivalent to the input term); identification (β-equivalent terms are mapped to the same result); and completeness (the function is defined for all terms that do have normal forms). We also show how the semantic construction enables a simple yet formal correctness proof for the normalization algorithm, expressed as a functional program in an ML-like, call-by-value language. Finally, we generalize the construction to produce an infinitary variant of normal forms, namely Böhm trees. We show that the three-part characterization of correctness, as well as the proofs, extend naturally to this generalization.

A unit disk graph is the intersection graphof a family of unit disks in the plane.If the disks do not overlap, it is also a unit coin graph or penny graph.It is known that finding a maximum independent setin a unit disk graph is a NP-hard problem.In this work we extend this result to penny graphs.Furthermore, we prove that finding a minimum clique partitionin a penny graph is also NP-hard, and presenttwo linear-time approximation algorithms for the computation of clique partitions:a 3-approximation algorithm for unit disk graphsand a 2-approximation algorithm for penny graphs.

The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length n which occur in the arithmetical subsequences of the infinite word. This is one of the modifications of the classical function of subword complexity, which is equal to the number of factors of the infinite word of length n. In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions. More precisely, for each sequence u of subword complexity ƒu(n) and for each prime p ≥ 3 we build a Toeplitz word on the same alphabet whose arithmetical complexity is $a(n)=\Theta(n f_u(\lceil \log_p n \rceil))$.

We introduce a domain-free λµ-calculus of call-by-value as a short-hand for the second order Church-style. Our motivation comes from the observation that in Curry-style polymorphic calculi, control operators such as callcc-operators cannot, in general, handle correctly the terms placed on the control operator's left, so that the Curry-style system can fail to prove the subject reduction property. Following the continuation semantics, we also discuss the notion of values in classical system, and propose an extended form of values. It is proved that the CPS-translation is sound with respect to domain-free λ2 (second-order λ-calculus). As a by-product, we obtain the strong normalization property for the second-order λµ-calculus of call-by-value in domain-free style. We also study the problems of type inference, typability, and type checking for the call-by-value system. Finally, we give a brief comparison with standard ML plus callcc, and discuss a natural way to avoid the unsoundness of ML with callcc.

Based on the formal framework of reaction systems by Ehrenfeucht and Rozenberg[Fund. Inform. 75 (2007) 263–280], reaction automata (RAs)have been introduced by Okubo et al. [Theoret. Comput. Sci.429 (2012) 247–257], as language acceptors with multiset rewritingmechanism. In this paper, we continue the investigation of RAs with a focus on the twomanners of rule application: maximally parallel and sequential. Considering restrictionson the workspace and the λ-input mode, we introduce the correspondingvariants of RAs and investigate their computation powers. In order to explore Turingmachines (TMs) that correspond to RAs, we also introduce a new variant of TMs withrestricted workspace, called s(n)-restricted TMs. Themain results include the following: (i) for a language L and a functions(n), L is accepted by ans(n)-bounded RA with λ-input mode insequential manner if and only if L is accepted by alog s(n)-bounded one-way TM; (ii) if a languageL is accepted by a linear-bounded RA in sequential manner, thenL is also accepted by a P automaton [Csuhaj−Varju and Vaszil, vol. 2597of Lect. Notes Comput. Sci. Springer (2003) 219–233.] in sequentialmanner; (iii) the class of languages accepted by linear-bounded RAs in maximally parallelmanner is incomparable to the class of languages accepted by RAs in sequential manner.

Recently, Constantinescu and Ilie proved a variant of the well-known periodicity theoremof Fine and Wilf in the case of two relatively prime abelian periods and conjectured aresult for the case of two non-relatively prime abelian periods. In this paper, we answersome open problems they suggested. We show that their conjecture is false but we givebounds, that depend on the two abelian periods, such that the conjecture is true for allwords having length at least those bounds and show that some of them are optimal. We alsoextend their study to the context of partial words, giving optimal lengths and describingan algorithm for constructing optimal words.

We investigate a Gentzen-style proof system for the first-order μ-calculusbased on cyclic proofs, produced by unfolding fixed point formulasand detecting repeated proof goals. Our system uses explicit ordinalvariables and approximations to support a simple semantic inductiondischarge condition which ensures the well-foundedness of inductivereasoning. As the main result of this paper we propose a new syntacticdischarge condition based on traces and establish its equivalencewith the semantic condition. We give an automata-theoretic reformulationof this condition which is more suitable for practical proofs. Fora detailed comparison with previous work we consider two simpler syntacticconditions and show that they are more restrictive than our new condition.

We consider the position and number of occurrences of squares in the Thue-Morse sequence, and show that the corresponding sequences are 2-regular. We also prove that changing any finite but nonzero number of bits in the Thue-Morse sequence creates an overlap, and any linear subsequence of the Thue-Morse sequence (except those corresponding to decimation by a power of 2) contains an overlap.

Ko [26] and Bruschi [11] independently showed that, insome relativized world, PSPACE (in fact, ⊕P) contains a setthat is immune to the polynomial hierarchy (PH). In this paper, westudy and settle the question of relativized separations withimmunity for PH and the counting classes PP, ${\rm C\!\!\!\!=\!\!\!P}$ , and ⊕Pin all possible pairwise combinations. Our main result is that thereis an oracle A relative to which ${\rm C\!\!\!\!=\!\!\!P}$ contains a set that is immune BPP⊕P.In particular, this ${\rm C\!\!\!\!=\!\!\!P}^A$ set is immune to PHA and to ⊕PA. Strengthening results ofTorán [48] and Green [18], we also show that, in suitable relativizations, NP contains a ${\rm C\!\!\!\!=\!\!\!P}$ -immune set, and ⊕P contains a PPPH-immune set. This implies the existence of a ${\rm C\!\!\!\!=\!\!\!P}^B$ -simple set for someoracle B, which extends results of Balcázar et al. [2,4].Our proof technique requires a circuit lower bound for “exactcounting” that is derived from Razborov's [35] circuitlower bound for majority.

In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word w from a given set I of substrings (fragments) of a word w. We introduce an hypothesis involving the set of fragments I and the maximal length m(w) of the minimal forbidden factors of w. Such hypothesis allows us to reconstruct uniquely the word w from the set I in linear time. We prove also that, if w is a word randomly generated by a memoryless source with identical symbol probabilities, m(w) is logarithmic with respect to the size of w. This result shows that our reconstruction algorithm is suited to approach the above problem in several practical applications e.g. in the case of DNA sequences.

This paper describes a modification of the power set construction for the transformation of self-verifying nondeterministic finite automata to deterministic ones. Using a set counting argument, the upper bound for this transformation can be lowered from $2^n$ to $O(\frac{2^n}{\sqrt{n}}).$