Monads have been employed in programming languages for modeling various language features, most importantly those that involve side effects. In particular, Haskell's IO monad provides access to I/O operations and mutable variables, without compromising referential transparency. Cyclic definitions that involve monadic computations give rise to the concept of value-recursion, where the fixed-point computation takes place only over the values, without repeating or losing effects. In this paper, we describe a semantics for a lazy language based on Haskell, supporting monadic I/O, mutable variables, usual recursive definitions, and value recursion. Our semantics is composed of two layers: a natural semantics for the functional layer, and a labeled transition semantics for the IO layer.

The repetition threshold introduced by Dejean and Brandenburg is the smallest real number α such that there exists an infinite word over a k-letter alphabet that avoids β-powers for all β > α. We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.

In the job shop scheduling problem k-units-J m , there are m machines and each machine has an integer processing time of at most k time units. Each job consists of a permutation of m tasks corresponding to all machines and thus all jobs have an identicaldilation D. The contribution of this paper are the following results;(i) for $d=o(\sqrt{D})$ jobs and every fixed k, the makespan of an optimal schedule is at most D+ o(D), which extends the result of [3]for k=1; (ii) a randomized on-line approximation algorithm for k-units-J m  ispresented. This is the on-line algorithm with the best known competitiveratio against an oblivious adversary for $d = o(\sqrt{D})$ and k > 1; (iii) different processing times yield harder instances than identicalprocessing times. There is no 5/3 competitive deterministic on-linealgorithm for k-units-J m , whereas the competitive ratio of the randomizedon-line algorithm of (ii) still tends to 1 for $d = o(\sqrt{D})$ .

More than a decade ago, Moller and Tofts published their seminal work on relating processes, which are annotated with lower time bounds, with respect to speed. Their paper has left open many questions regarding the semantic theory for the suggested bisimulation-based faster-than preorder, the MT-preorder, which have not been addressed since. The encountered difficulties concern a general compositionality result, a complete axiom system for finite processes, a convincing intuitive justification of the MT-preorder, and the abstraction from internal computation. This article solves these difficulties by developing and employing a novel commutation lemma relating the sequencing of action and clock transitions in discrete-time process algebra. Most importantly, it is proved that the MT-preorder is fully-abstract with respect to a natural amortized preorder that uses a simple bookkeeping mechanism for deciding whether one process is faster than another. Together these results reveal the intuitive roots of the MT-preorder as a faster-than relation, while testifying to its semantic elegance. This lifts some of the barriers that have so far hampered progress in semantic theories for comparing the speed of processes.

The basic framework of domain μ-calculus was formulated in [39] more than ten years ago.This paper provides an improved formulation of a fragment of the μ-calculus without function space or powerdomain constructions,and studies some open problemsrelated to this μ-calculus such asdecidability and expressive power.A class of language equations is introducedfor encoding μ-formulas in order toderive results related to decidability and expressive power of non-trivial fragments of the domain μ-calculus.The existence and uniqueness of solutions tothis class of language equations constitute an important component of this approach.Our formulation is based on the recent work of Leiss [23], who established a sophisticated framework for solving language equationsusing Boolean automata(a.k.a. alternating automata [12,35]) and a generalized notion of language derivatives.Additionally, the early notion of even-linear grammars is adopted here totreat another fragment of the domain μ-calculus.

We consider the languages of finite trees called tree-shift languages which are factorial extensible tree languages. These languages are sets of factors of subshifts of infinite trees. We give effective syntactic characterizations of two classes of regular tree-shift languages: the finite type tree languages and the tree languages which are almost of finite type. Each class corresponds to a class of subshifts of trees which is invariant by conjugacy. For this goal, we define a tree algebra which is finer than the classical syntactic tree algebra based on contexts. This allows us to capture the notion of constant tree which is essential in the framework of tree-shift languages.

We introduce two new classes of codes, namely adjacent codes and codes with finite interpreting delay. For each class, we establish an extension of the defect theorem.

Rauzy fractals are compact sets with fractal boundary that can be associated with any unimodular Pisot irreducible substitution. These fractals can be defined as the Hausdorff limit of a sequence of compact sets, where each set is a renormalized projection of a finite union of faces of unit cubes. We exploit this combinatorial definition to prove the connectedness of the Rauzy fractal associated with any finite product of three-letter Arnoux–Rauzy substitutions.

In this note we consider the longest word, which has periods p1,...,pn , and does not have the period gcd(p1,...,pn ).The length of such a word can be established by a simple algorithm. We give a short and natural way to prove that the algorithm is correct. We also give a new proof that the maximal word is a palindrome.

Coalgebras for endofunctors ${\mathcal C}\rightarrow{\mathcal C}$ can be used to model classes of object-oriented languages. However, binary methods do not fit directly into this approach. This paper proposes an extension of the coalgebraic framework, namely the use of extended polynomial functors${\mathcal C}^{op} \times {\mathcal C}\rightarrow{\mathcal C}$. This extension allows the incorporation of binary methods into coalgebraic class specifications. The paper also discusses how to define bisimulation and invariants for coalgebras of extended polynomial functors and proves many standard results.

Let I be a finite set of words and $\Rightarrow_I^*$ be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let $L_I^{\epsilon}$ be the set of words u such that $\epsilon \Rightarrow_I^* u$. We prove that the set I is unavoidable if and only if the relation $\Rightarrow_I^*$ is a well quasi-order on the set $L_I^{\epsilon}$. This result generalizes a theorem of [Ehrenfeucht et al.,Theor. Comput. Sci.27 (1983) 311–332]. Further generalizations are investigated.

A k-abelian cube is a word uvw, where the factors u, v, and w are either pairwise equal, or have the same multiplicities for every one of their factors of length at most k. Previously it has been shown that k-abelian cubes are avoidable over a binary alphabet for k ≥ 8. Here it is proved that this holds for k ≥ 5.

In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class $\#W[P]$, the parameterized analogue of $\#P$. We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.

We show that there are three types of infinite words over the two-letter alphabet {0,1} that avoid the pattern AABBCABBA. These types, P, E0, and E1, differ by the factor complexity and the asymptotic frequency of the letter 0. Type P has polynomial factor complexity and letter frequency $\frac{1}{2}$. Type E0 has exponential factor complexity and the frequency of the letter 0 is at least 0.45622 and at most 0.48684. Type E1 is obtained from type E0 by exchanging 0 and 1.

The cutwidth is an important graph-invariant in circuit layout designs. The cutwidth of agraph G is the minimum value of the maximum number of overlap edges whenG is embedded into a line. A caterpillar is a tree which yields a pathwhen all its leaves are removed. An iterated caterpillar is a tree which yields acaterpillar when all its leaves are removed. In this paper we present an exact formula forthe cutwidth of the iterated caterpillars.

Numerical integration is an important operation for scientific computations. Although the different quadrature methods have been well studied from a mathematical point of view, the analysis of the actual error when performing the quadrature on a computer is often neglected. This step is however required for certified arithmetics.
We study the Newton-Cotes quadrature scheme in the context of multiple-precision arithmetic and give enough details on the algorithms and the error bounds to enable software developers to write a Newton-Cotes quadrature with bounded error.

The avoidability of binary patterns by binary cube-free words is investigated and the exact bound between unavoidable and avoidable patterns is found. All avoidable patterns are shown to be D0L-avoidable. For avoidable patterns, the growth rates of the avoiding languages are studied. All such languages, except for the overlap-free language, are proved to have exponential growth. The exact growth rates of languages avoiding minimal avoidable patterns are approximated through computer-assisted upper bounds. Finally, a new example of a pattern-avoiding language of polynomial growth is given.

The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension $k\times k$ matrices with integer or rational entries is studied. We call these two problems $\sf IMP_k$ and $\sf MPOW_k$, respectively, for short. We prove that: (i) For $k\geq2$, $\sf IMP_k$ does not belong to ${\rm TC}^0$, unless ${\rm TC}^0={\rm NC}^1$.newline (ii) For stochastic matrices : $\sf IMP_2$ belongs to ${\rm TC}^0$ while, for $k\geq3$, $\sf IMP_k$ does not belong to ${\rm TC}^0$, unless ${\rm TC}^0={\rm NC}^1$. (iii) For any k, $\sf MPOW_k$ belongs to ${\rm TC}^0$.

The necessary and sufficient conditions are extracted for periodicity of bi-ideals. They cover infinitely and finitely generated bi-ideals.

We present a novel eye localization method which can be used in face recognition applications. It is based on two SVM classifiers which localize the eyes at different resolution levels exploiting the Haar wavelet representation of the images. We present an extensive analysis of its performance on images of very different public databases, showing very good results.