Safety- and liveness-properties in propositional temporal logic: characterizations and decidability
Sand pile automata
Satisfiability and computing van der Waerden numbers.
Saturating right congruences
Scheduling in the presence of processor networks : complexity and approximation
In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule ...
Scheduling in the presence of processor networks : complexity and approximation
In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule ...
Selected multicriteria shortest path problems: an analysis of complexity, models and adaptation of standard algorithms
The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multi-objective shortest path (MOSP) problems is given. Different models of MOSP problems are discussed in detail. Methods of solving the formulated optimization problems are presented. An analysis of the complexity of the presented methods and ways of adapting of classical algorithms for solving multiobjective shortest path problems are described. A comparison of the effectiveness...
Self-affine fractals of finite type
In the class of self-affine sets on ℝⁿ we study a subclass for which the geometry is rather tractable. A type is a standardized position of two intersecting pieces. For a self-affine tiling, this can be identified with an edge or vertex type. We assume that the number of types is finite. We study the topology of such fractals and their boundary sets, and we show how new finite type fractals can be constructed. For finite type self-affine tiles in the plane we give an algorithm which decides whether...
Selfgenerating sequences and different types of computational devices [Abstract of thesis]
Self-reducibility structures and solutions of NP problems.
Using polynomial time self-reducibility structures, we characterize certain helping notions, show how the characterization provides the main tool for the proof of known relationships between decisional and functional NP-complete problems, and extend this relationships to the case of optimization NP-complete problems.
Self-replication processes in nanosystems of informatics
Recent research on the nanotechnological processes of molecular products and object synthesis as well as research on the nanosystems of informatics, stimulates the development of technical systems of informatics. Until now, they have been used mainly for computational tasks when, similarly to biological organisms, they allowed the development of self-replicating products and complete objects. One can focus here on the model of a circulation of materials, information and energy in a biological cell,...
Self-reproducing pushdown transducers
After a translation of an input string, , to an output string, , a self- reproducing pushdown transducer can make a self-reproducing step during which it moves to its input tape and translates it again. In this self- reproducing way, it can repeat the translation -times for any . This paper demonstrates that every recursively enumerable language can be characterized by the domain of the translation obtained from a self- reproducing pushdown transducer that repeats its translation no more than...
Semantic analysis of an ALGOL text
Semantics of value recursion for monadic input/output
Monads have been employed in programming languages for modeling various language features, most importantly those that involve side effects. In particular, Haskell’s IO monad provides access to I/O operations and mutable variables, without compromising referential transparency. Cyclic definitions that involve monadic computations give rise to the concept of value-recursion, where the fixed-point computation takes place only over the values, without repeating or losing effects. In this paper, we...
Semantics of value recursion for Monadic Input/Output
Monads have been employed in programming languages for modeling various language features, most importantly those that involve side effects. In particular, Haskell's IO monad provides access to I/O operations and mutable variables, without compromising referential transparency. Cyclic definitions that involve monadic computations give rise to the concept of value-recursion, where the fixed-point computation takes place only over the values, without repeating or losing effects. In this paper,...
Sémantique algébrique de l'appel par valeur
Sémantique des processus communicants
Sémantique des structures de contrôle
Sémantique du parallélisme et du choix du langage Electre
Sémantique formelle des opérateurs d'un langage de listes