Sémantique logique et dénotationnelle des interpréteurs PROLOG
Semi-algebraic complexity-additive complexity of diagonalization of quadratic forms.
We study matrix calculations such as diagonalization of quadratic forms under the aspect of additive complexity and relate these complexities to the complexity of matrix multiplication. While in Bürgisser et al. (1991) for multiplicative complexity the customary thick path existence argument was sufficient, here for additive complexity we need the more delicate finess of the real spectrum (cf. Bochnak et al. (1987), Becker (1986), Knebusch and Scheiderer (1989)) to obtain a complexity relativization....
Semi-commutations and partial commutations
Semi-commutations and Partial commutations
The aim of this paper is to show that a semi-commutation function can be expressed as the compound of a sequential transformation, a partial commutation function, and the reverse transformation. Moreover, we give a necessary and sufficient condition for the image of a regular language to be computed by the compound of two sequential functions and a partial commutation function.
Semidefinite Programming Based Algorithms for the Sparsest Cut Problem
In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum...
Semidefinite Programming Based Algorithms for the Sparsest Cut Problem
In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum...
Semigroups defined by automaton extension mapping
We study semigroups generated by the restrictions of automaton extension (see, e.g., [3]) and give a characterization of automaton extensions that generate finite semigroups.
Semisimplicity of the algebra associated to a biprefix code.
Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
Separating from co-, and for oblivious Turing machines of linear access
Separating Two Simple Polygons by a Sequence of Translations.
Separating words with machines and groups
Sequential machines with several input and output tapes
Sequential mappings of -languages
Sequential monotonicity for restarting automata
As already 2-monotone R-automata accept NP-complete languages, we introduce a restricted variant of j-monotonicity for restarting automata, called sequential j-monotonicity. For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that RLWW-automata that are sequentially monotone of degree j for any j ≥ 1 only...
Séries algébriques solutions d'équations linéaires avec opérateurs
Séries formelles
La classification chomskienne des langages formels conduit à l'étude d'objets mathématiques nouveaux: les séries rationnelles et algébriques en variables non commutatives.
Séries formelles rationnelles et reconnaissables
Séries rationnelles
Séries rationnelles à plusieurs variables non commutatives, Hadamard-inversibles