The paper presents an elementary approach for the calculation of the entropy of a class of languages. This approach is based on the consideration of roots of a real polynomial and is also suitable for calculating the Bernoulli measure. The class of languages we consider here is a generalisation of the Łukasiewicz language.

It is known that the weakly monotone restarting automata acceptexactly the growing context-sensitive languages. We introduce ameasure on the degree of weak monotonicity and show that thelanguage classes obtained in this way form strict hierarchies forthe various types of deterministic and nondeterministic restartingautomata without auxiliary symbols.

We study the properties of the function R(n) which determines the number of representationsof an integer n as a sum of distinct Fibonacci numbers F k . We determine the maximum andmean values of R(n) for Fk ≤ n < Fk+1 .

Given a basis of pseudoidentities for a pseudovariety of ordered semigroups containing the 5-element aperiodic Brandt semigroup B2, under the natural order, it is shown that the same basis, over the most general graph over which it can be read, defines the global. This is used to show that the global of the pseudovariety of level 3/2 of Straubing-Thérien's concatenation hierarchy has infinite vertex rank.

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.

We give necessary and sufficient conditions for a language to be the language of finite words that occur infinitely many times in an infinite word.

We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity bound for the star height problem.

Among several alternative viewpoints for building software quality metrics, evaluating the consistency between different modelsin a software specification or implementation appears to be fruitful.An obvious difficulty is that different models are usually expressedby means of different concepts, and then, confronting heterogeneousrepresentations is not straightforward.In this paper, we propose a solution for measuring theconsistency between the architecture and the communication models.After some sensible transformations, the information about bothmodels are captured trough hierarchical representations. We defineand discuss a similarity measure between hierarchies, that eventuallyfounds the software metric we propose. Lastly, we investigate how toscale and interpret the metric values and give an application examplewith SDL.

We show that semigroups representable by triangular matrices over a fixed finite field form a decidable pseudovariety and provide a finite pseudoidentity basis for it.

Dans cet article, nous exploitons la réductibilité d'un polynôme d'une variable pour calculer efficacement l'idéal des relations algébriques entre ses racines.

Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also showthat membership for these grammars is complete in P (it was known that this problem is in P) and characterize thecomplexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membershipis complete in EXPTIME and hard for PSPACE for monotonicgrammars.

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 consider shifted equality sets of the form EG(a,g1,g2) = {ω | g1(ω) = ag2(ω)}, where g1 and g2 are nonerasing morphisms and a is a letter. We are interested in the family consisting of the languages h(EG(J)), where h is a coding and (EG(J)) is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language L ⊆ A* is a projection of a shifted equality set, that is, L = πA(EG(a,g1,g2)) for some (nonerasing) morphisms g1 and g2 and a letter a, where πA deletes the letters not in A. Then we deduce that recursively enumerable star languages coincide with the projections of equality sets.

We introduce adhesive categories, which are categories with structure ensuring that pushouts along monomorphisms are well-behaved, as well as quasiadhesive categories which restrict attention to regular monomorphisms. Many examples of graphical structures used in computer science are shown to be examples of adhesive and quasiadhesive categories. Double-pushout graph rewriting generalizes well to rewriting on arbitrary adhesive and quasiadhesive categories.


We study simulation of gate circuits in the infinite algebra of transients recently introduced by Brzozowski and Ésik. A transient is a word consisting of alternating 0s and 1s; it represents a changing signal. In the algebra of transients, gates process transients instead of 0s and 1s. Simulation in this algebra is capable of counting signal changes and detecting hazards. We study two simulation algorithms: a general one that works with any initial state, and a special one that applies only if the initial state is stable. We show that the two algorithms agree in the stable case. We also show that the general algorithm is insensitive to the removal of state variables that are not feedback variables. We prove the sufficiency of simulation: all signal changes occurring in binary analysis are predicted by the general algorithm. Finally, we show that simulation can be more pessimistic than binary analysis, if wire delays are not taken into account. We propose a circuit model that we conjecture to be sufficient for proving the equivalence of simulation and binary analysis for feedback-free circuits.


This paper provides a framework to address termination problems in term rewriting by using orderings induced by algebras over the reals. The generation of such orderings is parameterized by concrete monotonicity requirements which are connected with different classes of termination problems: termination of rewriting, termination of rewriting by using dependency pairs, termination of innermost rewriting, top-termination of infinitary rewriting, termination of context-sensitive rewriting, etc. We show how to define term orderings based on algebraic interpretations over the real numbers which can be used for these purposes. From a practical point of view, we show how to automatically generate polynomial algebras over the reals by using constraint-solving systems to obtain the coefficients of a polynomial in the domain of the real or rational numbers. Moreover, as a consequence of our work, we argue that software systems which are able to generate constraints for obtaining polynomial interpretations over the naturals which prove termination of rewriting (e.g., AProVE, CiME, and TTT), are potentially able to obtain suitable interpretations over the reals by just solving the constraints in the domain of the real or rational numbers.

We consider systems consisting of finite automata communicating by exchanging messagesand working on the same read-only data.We investigate the situation in which the automata work with constantbut different speeds. We assume furthermore that the automata are not aware of the speeds andthey cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata.Complexity measure that we consider here is the number of messages sent by the automata.The main result of this paper is that multi-speed systems are as powerful as synchronous systems, in whichall automata work with the same speed.

We investigate the structure of “worst-case” quasi reduced ordered decision diagrams and Boolean functions whose truth tables are associated to: we suggest different ways to count and enumerate them. We, then, introduce a notion of complexity which leads to the concept of “hard” Boolean functions as functions whose QROBDD are “worst-case” ones. So we exhibit the relation between hard functions and the Storage Access function (also known as Multiplexer).