We describe a technique that maps unranked trees to arbitrary hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to other hashing techniques based on automata, our procedure builds a pseudo-minimal DTA for this purpose. A pseudo-minimal automaton may be larger than the minimal one accepting the same language but, in turn, it contains proper elements (states or transitions which are unique) for every input accepted by the automaton. Therefore, pseudo-minimal DTA are a suitable structure to implement stable hashing schemes, that is, schemes where the output for every key can be determined prior to the automaton construction. We provide incremental procedures to build the pseudo-minimal DTA and the mapping that associates an integer value to every transition that will be used to compute the hash codes. This incremental construction allows for the incorporation of new trees and their hash codes without the need to rebuild the whole DTA from scratch.

Thread algebra is a semantics for recent object-oriented programming languages [J.A. Bergstra and M.E. Loots, J. Logic Algebr. Program.51 (2002) 125–156; J.A. Bergstra and C.A. Middelburg, Formal Aspects Comput. (2007)] such as C# and Java. This paper shows that thread algebra provides a process-algebraic framework for reasoning about and classifying various standard notions of noninterference, an important property in secure information flow. We will take the noninterference property given by Volpano et al. [D. Volpano, G. Smith and C. Irvine, J. Comput. Secur.4 (1996) 167–187] on type systems as an example of our approach. We define a comparable notion of noninterference in the setting of thread algebra. Our approach gives a similar result to the approach of [G. Smith and D. Volpano, in POPL'9829 (1998) 355–364] and can be applied to unstructured and multithreaded programming languages.

We study two topological properties of the 5-ary n-cube $Q_{n}^{5}$. Given two arbitrary distinct nodes x and y in $Q_{n}^{5}$, we prove that there exists an x-y path of every length ranging from 2n to 5n - 1, where n ≥ 2. Based on this result, we prove that $Q_{n}^{5}$ is 5-edge-pancyclic by showing that every edge in $Q_{n}^{5}$ lies on a cycle of every length ranging from 5 to 5n.

We propose a new way of characterizing the complexity of online problems. Instead of measuring the degradation of the output quality caused by the ignorance of the future we choose to quantify the amount of additional global information needed for an online algorithm to solve the problem optimally. In our model, the algorithm cooperates with an oracle that can see the whole input. We define the advice complexity of the problem to be the minimal number of bits (normalized per input request, and minimized over all algorithm-oracle pairs) communicated by the algorithm to the oracle in order to solve the problem optimally. Hence, the advice complexity measures the amount of problem-relevant information contained in the input. We introduce two modes of communication between the algorithm and the oracle based on whether the oracle offers an advice spontaneously (helper) or on request (answerer). We analyze the Paging and DiffServ problems in terms of advice complexity and deliver upper and lower bounds in both communication modes; in the case of DiffServ problem in helper mode the bounds are tight.

We prove that every Sturmian word ω has infinitely many prefixes of the form UnVn3, where |Un| < 2.855|Vn| and limn→∞|Vn| = ∞. In passing, we give a very simple proof of the known fact that every Sturmian word begins in arbitrarily long squares.

We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.

We study the palindromic complexity of infinite words uβ, the fixed points of the substitution over a binary alphabet, φ(0) = 0a1, φ(1) = 0b1, with a - 1 ≥ b ≥ 1, which are canonically associated with quadratic non-simple Parry numbers β.

We present an on-line linear time and space algorithmto check if an integer array f is the border array of at least one string w built on a boundedor unbounded size alphabet Σ. First of all, we show a bijection between the border array of a string w and the skeleton of the DFA recognizing Σ*ω, called a string matching automaton (SMA).Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array anda skeleton of SMA is independent from the underlying strings. This enables to design algorithms for validating and generating border arrays that outperform existing ones.The validating algorithm lowers the delay (maximal number of comparisons onone element of the array) from O(|w|) to 1 + min{|Σ|,1 + log2|ω|}compared to existing algorithms.We then give results on the numbers of distinct border arrays depending on the alphabet size.We also present an algorithm that checks if a given directed unlabeled graph G is the skeleton of aSMA on an alphabet of size s in linear time.Along the process the algorithm can build one string w for which G is the SMA skeleton.

We show that any positive integer is the least period of a factor of the Thue-Morse word. We also characterize the set of least periods of factors of a Sturmian word. In particular, the corresponding set for the Fibonacci word is the set of Fibonacci numbers. As a by-product of our results, we give several new proofs and tightenings of well-known properties of Sturmian words.

Labelling problems for graphs consist in building distributed data structures, making it possible to check a given graph property or to compute a given function, the arguments of which are vertices. For an inductively computable function D, if G is a graph with n vertices and of clique-width at most k, where k is fixed, we can associate with each vertex x of G a piece of information (bit sequence) lab(x) of length O(log2(n)) such that we can compute D in constant time, using only the labels of its arguments. The preprocessing can be done in time O(h.n) where h is the height of the syntactic tree of G. We perform an inductive computation, without using the tools of monadic second order logic. This enables us to give an explicit labelling scheme and to avoid constants of exponential size.

Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing the same episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As a consequence of these results, we characterize episturmian words having a unique directive word.

It is shown that the class of left-to-right regular languages coincides with the class of languages that are accepted by monotone deterministic RL-automata, in this way establishing a close correspondence between a classical parsing algorithm and a certain restricted type of analysis by reduction.

We show that the inclusion problem is decidable for rational languages of words indexed by scattered countable linear orderings. The method leans on a reduction to the decidability of the monadic second order theory of the infinite binary tree [9].

We show that many classical decision problems about1-counter ω-languages, context free ω-languages, or infinitary rational relations, are Π½ -complete, hence located at the second level of the analytical hierarchy, and “highly undecidable”.In particular, the universalityproblem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and theunambiguity problem are all Π½ -complete for context-free ω-languages or for infinitary rational relations. Topological and arithmetical properties of1-counter ω-languages, context free ω-languages, or infinitary rational relations, are also highly undecidable.These very surprising results provide the first examples of highly undecidable problems about the behaviour of verysimple finite machines like 1-counter automata or 2-tapeautomata.

This paper discusses context-free rewriting systems inwhich there exist two disjoint finite sets of rules, and a symbol, referred to as a condition of applicability, is attached to each rule in either of these two sets. In one set, a rule with a symbol attached to it is applicable if the attached symbol occurs in the current rewritten string while in the other set, such a rule is applicable if the attached symbol does not occur there. The present paper demonstrates that these rewriting systems are computationally complete. From this main result, the paper derives several consequences and solves several open problems.

In the XML standard, data are represented as unranked labeledordered trees. Regular unranked tree automata provide a usefulformalism for the validation of schemas enforcing regular structuralconstraints on XML documents. However some concrete applicationcontexts need the expression of more general constraints than theregular ones. In this paper we propose a new framework in whichcontext-free style structural constraints can be expressed andvalidated. This framework is characterized by: (i) the introductionof a new notion of trees, the so-called typed unranked labeledtrees (tulab trees for short) in which each node receivesone of three possible types (up, down or fix), and (ii) thedefinition of a new notion of tree automata, the so-callednested sibling tulab tree automata, able to enforcecontext-free style structural constraints on tulab tree languages.During their structural control process, such automata are usingvisibly pushdown languages of words [R. Alur and P. Madhusudan, Visibly pushdown languages, 36th ACM symposium on Theory of Computing, Chicago, USA (2004) 202–211] on theiralphabet of states. We show that the resulting class NSTL oftulab tree languages recognized by nested sibling tulab treeautomata is robust, i.e. closed under Boolean operations and withdecision procedures for the classical membership, emptiness andinclusion problems. We then give three characterizations of NSTL :a logical characterization by defining an adequate logic in whichNSTL happens to coincide with the models of monadic second ordersentences; the two other characterizations are using adequateencodings and map together languages of NSTL with some regularsets of 3-ary trees or with particular sets of binary trees.