We introduce in this article a new method to calculate all absolute andrelatif primitive invariants of finite groups. This method is inspiredfrom K. Girstmair which calculate an absolute primitive invariant ofminimal degree.Are presented two algorithms, the first one enable us to calculate allprimitive invariants of minimal degree, and the second one calculate allabsolute or relative primitive invariants with distincts coefficients. Thiswork take place in Galois Theory and Invariant Theory.

Ko [26] and Bruschi [11] independently showed that, insome relativized world, PSPACE (in fact, ⊕P) contains a setthat is immune to the polynomial hierarchy (PH). In this paper, westudy and settle the question of relativized separations withimmunity for PH and the counting classes PP, ${\rm C\!\!\!\!=\!\!\!P}$ , and ⊕Pin all possible pairwise combinations. Our main result is that thereis an oracle A relative to which ${\rm C\!\!\!\!=\!\!\!P}$ contains a set that is immune BPP⊕P.In particular, this ${\rm C\!\!\!\!=\!\!\!P}^A$ set is immune to PHA and to ⊕PA. Strengthening results ofTorán [48] and Green [18], we also show that, in suitable relativizations, NP contains a ${\rm C\!\!\!\!=\!\!\!P}$ -immune set, and ⊕P contains a PPPH-immune set. This implies the existence of a ${\rm C\!\!\!\!=\!\!\!P}^B$ -simple set for someoracle B, which extends results of Balcázar et al. [2,4].Our proof technique requires a circuit lower bound for “exactcounting” that is derived from Razborov's [35] circuitlower bound for majority.

String rewriting reductions of the form $t\to_R^+ utv$ , called loops, are the most frequent cause of infinite reductions (non-termination). Regarded as a model of computation, infinite reductions are unwanted whence their static detection is important. There are string rewriting systems which admit infinite reductions although they admit no loops. Their non-termination is particularly difficult to uncover. We present a few necessary conditions for the existence of loops, and thus establish a means to recognize the difficult case. We show in detail four relevant criteria: (i) the existence of loops is characterized by the existence of looping forward closures; (ii) dummy elimination, a non-termination preserving transformation method, also preserves the existence of loops; (iii) dummy introduction, a transformation method that supports subsequent dummy elimination, likewise preserves loops; (iv) bordered systems can be reduced to smaller systems on a larger alphabet, preserving the existence and the non-existence of loops. We illustrate the power of the four methods by giving a two-rule string rewriting system over a two-letter alphabet which admits an infinite reduction but no loop. So far, the least known such system had three rules.

In Hoare's (1961) original version of the algorithm  the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question.Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergencein distribution of the number of comparisons required and obtain a simple explicit result for the limitingaverage performance of the median-of-three version.

We consider numeration systems where the base is anegative integer, or a complex number which is a root of anegative integer.We give parallel algorithms for addition in these numeration systems,from which we derive on-line algorithms realized by finite automata. A general construction relating addition in base βand addition in base βm is given.Results on addition in base $\beta=\sqrt[m]{b}$ , where b is a relative integer, follow.We also show that addition in base the golden ratiois computable by an on-line finite automaton, but is notparallelizable.

An illustration of coinduction in terms of a notion of weak bisimilarity is presented. First, an operational semantics $\mbox{${\cal O}$}$ for while programs is defined in terms of a final automaton. It identifies any two programs that are weakly bisimilar, and induces in a canonical manner a compositional model $\mbox{${\cal D}$}$. Next $\mbox{${\cal O}$}= \mbox{${\cal D}$}$ is proved by coinduction.

In [6] it was shown that shuffle languagesare contained in one-way-NSPACE(log n) and in P.In this paper we show that nondeterministic one-way logarithmic spaceis in some sense the lower bound for accepting shuffle languages.Namely, we show that there exists a shuffle language which is notaccepted by any deterministic one-way Turing machine with space bounded bya sublinear function, and that there exists a shuffle language which isnot accepted with less than logarithmic space even if we allow two-waynondeterministic Turing machines.

Communication complexity of two-party (multiparty)protocols has established itself as a successful method for proving lower bounds on the complexity of concrete problems for numerous computing models. While the relations between communication complexity and oblivious, semilective computations are usually transparent and the main difficulty is reduced to proving nontrivial lower bounds on the communication complexity of given computing problems, the situation essentially changes, if one considers non-oblivious or multilective computations. The known lower bound proofs for such computations are far from being transparent and the crucial ideas of these proofs are often hidden behind some nontrivial combinatorial analysis. The aim of this paper is to create a general framework for the use of two-party communication protocols for lower bound proofs on multilective computations. The result of this creation is not only a transparent presentation of some known lower bounds on the complexity of multilective computations on distinct computing models, but also the derivation of new nontrivial lower bounds on multilective VLSI circuits and multilective planar Boolean circuits.In the case of VLSI circuits we obtain a generalization ofThompson's lower bounds on AT 2 complexity for multilective circuits.The Ω(n 2) lower bound on the number of gates of any k-multilectiveplanar Boolean circuit computing a specific Boolean function of n variablesis established for $k<\frac{1}{2} \log_2 n$ . Another advantage of this framework is that it provides lower bounds for a lot of concrete functions. This contrasts to the typical papersdevoted to lower bound proofs, where one establishes a lower bound for one or a few specific functions.

The study of inductive and coinductive types (like finite lists and streams, respectively) is usually conducted within the framework of category theory, which to all intents and purposes is a theory of sets and functions between sets. Allegory theory, an extension of category theory due to Freyd, is better suited to modelling relations between sets as opposed to functions between sets. The question thus arises of how to extend the standard categorical results on the existence of final objects in categories (for example, coalgebras and products) to their existence in allegories. The motivation is to streamline current work on generic programming, in which the use of a relational theory rather than a functional theory has proved to be desirable. In this paper, we define the notion of a relational final dialgebra and prove, for an important class of dialgebras, that a relational final dialgebra exists in an allegory if and only if a final dialgebra exists in the underlying category of maps. Instances subsumed by the class we consider include coalgebras and products. An important lemma expresses bisimulations in allegorical terms and proves this equivalent to Aczel and Mendler's categorical definition.

For every fixed-point expression e of alternation-depth r, we construct a new fixed-point expression e' of alternation-depth 2 and size ${\cal O}(r\cdot|e|)$. Expression e' is equivalent to e whenever operators are distributive and the underlying complete lattice has a co-continuous least upper bound. We alternation-depth but also w.r.t. the increase in size of the resulting expression.

An alternative (tree-based) semantics for a class of regular expressions is proposed that assigns a central rôle to the + operator and thus to nondeterminism and nondeterministic choice. For the new semantics a consistent and complete axiomatization is obtained from the original axiomatization of regular expressions by Salomaa and by Kozen by dropping the idempotence law for + and the distribution law of • over +.

We present a categorical formulation of the rewriting of possibly cyclic term graphs, based on a variation of algebraic 2-theories. We show that this presentation is equivalent to the well-accepted operational definition proposed by Barendregt et al. – but for the case of circular redexes , for which we propose (and justify formally) a different treatment. The categorical framework allows us to model in a concise way also automatic garbage collection and rules for sharing/unsharing and folding/unfolding of structures, and to relate term graph rewriting to other rewriting formalisms.