The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke andRueß. Natural variants of the PA arise from viewing a PA equivalently as an automaton thatkeeps a count of its transitions and semilinearly constrains their numbers. Here we adoptthis view and define the affine PA, that extends the PA by having eachtransition induce an affine transformation on the PA registers, and the PA onletters, that restricts the PA by forcing any two transitions on the sameletter to affect the registers equally. Then we report on the expressiveness, closure, anddecidability properties of such PA variants. We note that deterministic PA are strictlyweaker than deterministic reversal-bounded counter machines.

Threshold languages, which are the (k/(k–1))+-free languages over k-letter alphabets with k ≥ 5, are the minimal infinite power-free languages according to Dejean's conjecture, which is now proved for all alphabets. We study the growth properties of these languages. On the base of obtained structural properties and computer-assisted studies we conjecture that the growth rate of complexity of the threshold language over k letters tends to a constant $\hat{\alpha}\approx1.242$ as k tends to infinity.

Under the assumption that the Polynomial-TimeHierarchy does not collapsewe show for a regular language L:the unbalanced polynomial-time leaf language class determined by L equals  iff L is existentially but notquantifierfree definable in FO[<, min, max, +1, −1].Furthermore, no suchclass lies properly between NP and co-1-NP or NP⊕co-NP. The proofs rely on a result of Pin and Weilcharacterizing the automata of existentially first-order definable languages.

We consider languages expressed by word equations in two variables and give a complete characterization for their complexity functions, that is, the functions that give the number of words of the same length. Specifically, we prove that there are only five types of complexities: constant, linear, exponential, and two in between constant and linear. For the latter two, we give precise characterizations in terms of the number of solutions of Diophantine equations of certain types. In particular, we show that the linear upper bound on the non-exponential complexities by Karhumäki et al. in [9], is tight. There are several consequences of our study. First, we derive that both of the sets of all finite Sturmian words and of all finite Standard words are expressible by word equations. Second, we characterize the languages of non-exponential complexity which are expressible by two-variable word equations as finite unions of several simple parametric formulae and solutions of a two-variable word equation with a finite graph. Third, we find optimal upper bounds on the solutions of (solvable) two-variable word equations, namely, linear bound for one variable and quadratric for the other. From this, we obtain an $\mathcal{O}(n^6)$ algorithm for testing the solvability of two-variable word equations, improving thus very much Charatonik and Pacholski's $\mathcal{O}(n^100)$ algorithm from [3].

Foundations of the notion of quantum Turing machines areinvestigated. According to Deutsch's formulation, the time evolution of a quantum Turing machine is to be determined by the localtransition function. In this paper, the local transition functions are characterized for fully general quantum Turing machines, including multi-tape quantum Turing machines, extending the results due to Bernstein and Vazirani.

We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.e., a numerical value separating k-avoidable and k-unavoidable Abelian powers for each size k of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional power. We develop a method estimating the exponential growth rate of Abelian-power-free languages. Using this method, we get non-trivial lower bounds for Abelian repetition threshold for small alphabets. We suggest that some of the obtained bounds are the exact values of Abelian repetition threshold. In addition, we provide upper bounds for the growth rates of some particular Abelian-power-free languages.

The question of how to combine monads arises naturally in many areas with much recent interest focusing on the coproduct of two monads. In general, the coproduct of arbitrary monads does not always exist. Although a rather general construction was given by Kelly  [Bull.  Austral. Math. Soc.22 (1980) 1–83], its generality is reflected in its complexity which limits the applicability of this construction. Following our own research [C. Lüth and N. Ghani, Lect. Notes Artif. Intell.2309 (2002) 18–32], and that of Hyland, Plotkin and Power [IFIP Conf. Proc.223 (2002) 474–484], we are looking for specific situations when simpler constructions are available. This paper uses fixed points to give a simple construction of the coproduct of two ideal monads.

We survey several quantitative problems on infinite words related to repetitions, recurrence, and palindromes, for which the Fibonacci word often exhibits extremal behaviour.

For finitary set functors preserving inverse images, recursive coalgebras A of Paul Taylor are proved to be precisely those for which the system described by A always halts in finitely many steps.

It is well known that, given an endofunctor H on a category C , the initial (A+H-)-algebras (if existing), i.e. , the algebras of (wellfounded) H-terms over different variable supplies A, give rise to a monad with substitution as the extension operation (the free monad induced by the functor H). Moss [17] and Aczel, Adámek, Milius and Velebil [12] have shown that a similar monad, which even enjoys the additional special property of having iterations for all guarded substitution rules (complete iterativeness), arises from the inverses of the final (A+H-)-coalgebras (if existing), i.e. , the algebras of non-wellfounded H-terms. We show that, upon an appropriate generalization of the notion of substitution, the same can more generally be said about the initial T'(A,-)-algebras resp. the inverses of the final T'(A,-)-coalgebras for any endobifunctor T' on any category Csuch that the functors T'(-,X) uniformly carry a monad structure.

We show that, for any stochastic event p of period n, there exists a measure-once one-way quantum finite automaton (1qfa) with at most $2\sqrt{6n}+25$ states inducing the event ap+b, for constants a>0, b ≥ 0, satisfying a+b ≥ 1. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period n can be accepted with isolated cut point by a 1qfa with no more than $2\sqrt{6n}+26$ states. Our results give added evidence of the strength of measure-once 1qfa's with respect to classical automata.

Let P be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to P is also in P. Extending the classical Morse-Hedlund theorem, we show that either P contains at least n+1 words of length n for every n or, for some N, it contains at most N words of length n for every n. More importantly, we prove the following quantitative extension of this result: if P has m ≤ n words of length n then, for every k ≥ n + m, it contains at most ⌈(m + 1)/2⌉⌈(m + 1)/2⌈ words of length k.

We prove a long standing conjecture of Duval in the special case of Sturmian words.

We introduce a notion of category with feedback-with-delay, closely related to the notion of traced monoidal category, and show that the Circ construction of [15] is the free category with feedback on a symmetric monoidal category. Combining with the Int construction of Joyal et al. [12] we obtain a description of the free compact closed category on a symmetric monoidal category. We thus obtain a categorical analogue of the classical localization of a ring with respect to a multiplicative subset. In this context we define a notion of fixed-point semantics of a category with feedback which is seen to include a variety of classical semantics in computer science.

We study the complexity of the infinite word uβ associated with theRényi expansion of 1 in an irrational base β > 1.When β is the golden ratio, this is the well known Fibonacci word,which is Sturmian, and of complexity C(n) = n + 1.For β such thatdβ(1) = t1t2...tm is finite we provide a simple description ofthe structure of special factors of the word uβ . When tm =1we show thatC(n) = (m - 1)n + 1. In the cases when t1 = t2 = ... tm-1 ort1 > max{t2,...,tm-1 } we show that the first differenceof the complexity function C(n + 1) - C(n ) takes value in{m - 1,m} for every n, and consequently we determine thecomplexity of uβ . We show thatuβ is an Arnoux-Rauzy sequence if and only ifdβ(1) = tt...t1. On the example ofβ = 1 + 2cos(2π/7), solution of X3 = 2X2 + X - 1, we illustratethat the structure of special factors is more complicated fordβ (1) infinite eventually periodic.The complexity for this word is equal to 2n+1.

We propose a variation of Wythoff's game on three piles of tokens, in the sense that the losing positions can be derived from the Tribonacci word instead of the Fibonacci word for the two piles game. Thanks to the corresponding exotic numeration system built on the Tribonacci sequence, deciding whether a game position is losing or not can be computed in polynomial time.

Here is presented a 6-states non minimal-time solution which is intrinsically Minsky-like and solves the three following problems: unrestricted version on a line, with one initiator at each end of a line and the problem on a ring. We also give a complete proof of correctness of our solution, which was never done in a publication for Minsky's solutions.

The aim of this paper is to study the threshold behavior for the satisfiability property of a random k-XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with k variables per equation. For k ≥ 3 we show the existence of a sharp threshold for the satisfiability of a random k-XOR-CNF formula, whereas there are smooth thresholds for k=1 and k=2.

We give a partial answer to a question of Carlitz asking for a closed formula for the number of distinct representations of an integer in the Fibonacci base.

Floating-point arithmetic provides a fast but inexact way of computing geometric predicates. In order for these predicates to be exact, it is important to rule out all the numerical situations where floating-point computations could lead to wrong results. Taking into account all the potential problems is a tedious work to do by hand. We study in this paper a floating-point implementation of a filter for the orientation-2 predicate, and how a formal and partially automatized verification of this algorithm avoided many pitfalls. The presented method is not limited to this particular predicate, it can easily be used to produce correct semi-static floating-point filters for other geometric predicates.