Codd defined the relational algebra [E.F. Codd, Communications of the ACM13 (1970) 377–387;E.F. Codd, Relational completeness of data base sublanguages, in Data Base Systems, R. Rustin, Ed., Prentice-Hall (1972) 65–98] as the algebra with operations projection, join, restriction, union and difference. His projection operator can drop, permute and repeat columns of a relation. This permuting and repeating of columns does not really add expressive power to the relational algebra. Indeed, using the join operation, one can rewrite any relational algebra expression into an equivalent expression where no projection operator permutes or repeats columns. The fragment of the relational algebra known as the semijoin algebra, however, lacks a full join operation. Nevertheless, we show that any semijoin algebra expression can still be simulated in a natural way by a set of expressions where no projection operator permutes or repeats columns.

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})$ .

We consider relational periods, where the relation is acompatibility relation on words induced by a relation on letters. Weprove a variant of the theorem of Fine and Wilf for a (pure) periodand a relational period.

In this paper, we define the notion of biRFSA which is a residual finate stateautomaton (RFSA) whose the reverse is also an RFSA. The languages recognized bysuch automata are called biRFSA languages. We prove that the canonical RFSA of abiRFSA language is a minimal NFA for this language and that each minimalNFA for this language is a sub-automaton of the canonical RFSA. This leadsto a characterization of the family of biRFSA languages.In the second part of this paper, we define the family of biseparable automata. We prove that every biseparable NFA is uniquely minimal among all NFAs recognizinga same language, improving the result of H. Tamm and E. Ukkonen for bideterministic automata.

In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1, and n items of Q different classes, each item e with class ce and size se. The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size d. In a shelf bin packing problem, we have to obtain a shelf packing such that the total size of items and shelf divisors in any bin is at most 1. A dual approximation scheme must obtain a shelf packing of all items into N bins, such that, the total size of all items and shelf divisors packed in any bin is at most 1 + ε for a given ε > 0 and N is the number of bins used in an optimum shelf bin packing problem. Shelf divisors are used to avoid contact between items of different classes and can hold a set of items until a maximum given weight. We also present a dual approximation scheme for the class constrained bin packing problem. In this problem, there is no use of shelf divisors, but each bin uses at most C different classes.

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 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 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.

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.

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.