No description available.

We study the decidability and complexity of verification problems for infinite-state systems. A fundamental question in formal verification is if the behaviour of one process is reproducible by another. This inclusion problem can be studied for various models of computation and behavioural preorders. It is generally intractable or even undecidable already for very limited computational models. The aim of this work is to clarify the status of the decidability and complexity of some well-known inclusion problems for suitably restricted computational models. In particular, we address the problems of checking strong and weak simulation and trace inclusion for processes definable by one-counter automata (OCA), that consist of a finite control and a single counter ranging over the non-negative integers. We take special interest of the subclass of one-counter nets (OCNs), that cannot fully test the counter for zero and which is subsumed both by pushdown automata and Petri nets / vector addition systems. Our new results include the PSPACE-completeness of strong and weak simulation, and the undecidability of trace inclusion for OCNs. Moreover, we consider semantic preorders between OCA/OCN and finite systems and close some gaps regarding their complexity. Finally, we study deterministic processes, for which simulation and trace inclusion coincide.

Rotational hydraulic actuators, e.g. motors, provide infinite stroke as there is no conceptual limit to how far they can turn. By contrast linear hydraulic actuators like cylinders provide only limited stroke by concept. In the world of electrical drives, linear motors provide infinite stroke also for linear motion. In hydraulics, the presented Hydraulic Infinite Linear Actuator is a novelty. This paper presents the novel Hydraulic Infinite Linear Actuator (HILA). The contribution is an assessment of properties relevant for control like high hydraulic stiffness and is based on analysis, simulation and measurements.

<p>The complex behavior of computer systems offers many challenges for <i>formal verification</i>. The analysis quickly becomes difficult as the number of participating processes increases.</p><p>A <i>parameterized system</i> is a family of systems parameterized on a number <i>n</i>, typically representing the number of participating processes. The <i>uniform verification problem</i> — to check whether a property holds for each instance — is an infinite-state problem. The automated analysis of parameterized and infinite-state systems has been the subject of research over the last 15–20 years. Much of the work has focused on safety properties. Progress in verification of liveness properties has been slow, as it is more difficult in general.</p><p>In this thesis, we consider verification of parameterized and infinite-state systems, with an emphasis on liveness, in the verification framework called <i>regular model checking (RMC)</i>. In RMC, states are represented as words, sets of states as regular expressions, and the transition relation as a regular relation.</p><p>We extend the automata-theoretic approach to RMC. We define a <i>specification logic</i> sufficiently strong to specify systems representable using RMC, and linear temporal logic properties of such systems, and provide an automatic translation from a specification into an analyzable model.</p><p>We develop <i>acceleration techniques</i> for RMC which allow more uniform and automatic verification than before, with greater power. Using these techniques, we succeed to verify safety and liveness properties of parameterized protocols from the literature.</p><p>We present a novel <i>reachability based</i> verification method for verification of liveness, in a general setting. We implement the method for RMC, with promising results.</p><p>Finally, we develop a framework for the verification of dynamic networks based on graph transformation, which generalizes the systems representable in RMC. In this framework we verify the latest version of the DYMO routing protocol, currently being considered for standardization by the IETF.</p>

Electronic dispersion compensation (EDC) of intermodal dispersion on short multimode fiber (MMF) links operating at 40 Gb/s is investigated through system level simulations and the design of two analog integrated circuit (IC) equalizers. System simulations using worst-case MMF link models show the effectiveness of a 2-tap baud spaced finite impulse response (FIR) equalizer for 40-m links, and a second-order Tbaud/2 infinite impulse response (IIR) equalizer for 50-m links. An IIR filter topology suitable for IC implementation with double loops and multiple delay sections was developed. The 2-tap FIR and the IIR equalizer are implemented in UMC 0.13-um and STM 90-nm CMOS processes respectively. Measurements demonstrate the FIR and IIR equalizing 38-Gb/s and 30-Gb/s cable channels respectively. To the author's knowledge, the double-loop multi-delay IIR equalizer is the first integrated traveling-wave equalizer utilizing poles as a means of frequency boosting, contrasting the conventional FIR technique of utilizing zeros.

Electronic dispersion compensation (EDC) of intermodal dispersion on short multimode fiber (MMF) links operating at 40 Gb/s is investigated through system level simulations and the design of two analog integrated circuit (IC) equalizers. System simulations using worst-case MMF link models show the effectiveness of a 2-tap baud spaced finite impulse response (FIR) equalizer for 40-m links, and a second-order Tbaud/2 infinite impulse response (IIR) equalizer for 50-m links. An IIR filter topology suitable for IC implementation with double loops and multiple delay sections was developed. The 2-tap FIR and the IIR equalizer are implemented in UMC 0.13-um and STM 90-nm CMOS processes respectively. Measurements demonstrate the FIR and IIR equalizing 38-Gb/s and 30-Gb/s cable channels respectively. To the author's knowledge, the double-loop multi-delay IIR equalizer is the first integrated traveling-wave equalizer utilizing poles as a means of frequency boosting, contrasting the conventional FIR technique of utilizing zeros.

We consider infinite-dimensional diffusions where the interaction between the coordinates has a finite extent both in space and time. In particular, it is not supposed to be smooth or Markov. The initial state of the system is Gibbs, given by a strong summable interaction. If the strongness of this initial interaction is lower than a suitable level, and if the dynamical interaction is bounded from above in a right way, we prove that the law of the diffusion at any time t is a Gibbs measure with absolutely summable interaction. The main tool is a cluster expansion in space uniformly in time of the Girsanov factor coming from the dynamics and exponential ergodicity of the free dynamics to an equilibrium product measure.

Model checking is a fully-automatic formal verification method that has been extremely successful in validating and verifying safety-critical systems in the past three decades. In the past fifteen years, there has been a lot of work in extending many model checking algorithms over finite-state systems to finitely representable infinitestate systems. Unlike in the case of finite systems, decidability can easily become a problem in the case of infinite-state model checking. In this thesis, we present generic and specific techniques that can be used to derive decidability with near-optimal computational complexity for various model checking problems over infinite-state systems. Generic techniques and specific techniques primarily differ in the way in which a decidability result is derived. Generic techniques is a “top-down” approach wherein we start with a Turing-powerful formalismfor infinitestate systems (in the sense of being able to generate the computation graphs of Turing machines up to isomorphisms), and then impose semantic restrictions whereby the desired model checking problem becomes decidable. In other words, to show that a subclass of the infinite-state systems that is generated by this formalism is decidable with respect to the model checking problem under consideration, we will simply have to prove that this subclass satisfies the semantic restriction. On the other hand, specific techniques is a “bottom-up” approach in the sense that we restrict to a non-Turing powerful formalism of infinite-state systems at the outset. The main benefit of generic techniques is that they can be used as algorithmic metatheorems, i.e., they can give unified proofs of decidability of various model checking problems over infinite-state systems. Specific techniques are more flexible in the sense they can be used to derive decidability or optimal complexity when generic techniques fail. In the first part of the thesis, we adopt word/tree automatic transition systems as a generic formalism of infinite-state systems. Such formalisms can be used to generate many interesting classes of infinite-state systems that have been considered in the literature, e.g., the computation graphs of counter systems, Turing machines, pushdown systems, prefix-recognizable systems, regular ground-tree rewrite systems, PAprocesses, order-2 collapsible pushdown systems. Although the generality of these formalisms make most interesting model checking problems (even safety) undecidable, they are known to have nice closure and algorithmic properties. We use these nice properties to obtain several algorithmic metatheorems over word/tree automatic systems, e.g., for deriving decidability of various model checking problems including recurrent reachability, and Linear Temporal Logic (LTL) with complex fairness constraints. These algorithmic metatheorems can be used to uniformly prove decidability with optimal (or near-optimal) complexity of various model checking problems over many classes of infinite-state systems that have been considered in the literature. In fact, many of these decidability/complexity results were not previously known in the literature. In the second part of the thesis, we study various model checking problems over subclasses of counter systems that were already known to be decidable. In particular, we consider reversal-bounded counter systems (and their extensions with discrete clocks), one-counter processes, and networks of one-counter processes. We shall derive optimal complexity of various model checking problems including: model checking LTL, EF-logic, and first-order logic with reachability relations (and restrictions thereof). In most cases, we obtain a single/double exponential reduction in the previously known upper bounds on the complexity of the problems.

Les chercheurs savent depuis longtemps que la supraconductivité est engendrée par le couplage de paires d’électrons, appelées paires de Cooper. Par contre, l’origine de l’inter-action conduisant à l’attraction effective entre les électrons formant les paires demeure mal comprise pour certains matériaux découverts durant les trente dernières années. Dans ce mémoire, la supraconductivité a été induite dans des cuprates dopés aux électrons faisant partie de la famille des infinite-layers (IL), ayant la forme Sr[indice inférieur 1−x]Nd[indice inférieur x]CuO[indice inférieur 2]. Les IL ne peuvent être déposés en couches minces par la technique d’ablation laser que depuis très récemment. L’étude systématique de ces composés reste donc entièrement à accomplir. Les IL ont également une structure cristalline extrêmement simplifiée qui facilite l’interprétation des phénomènes physiques mesurés en laboratoire. L’étude des IL est un véritable tour de force. Plusieurs groupes de recherche dans le monde tentent de les synthétiser en couches minces avec beaucoup de difficulté. Ces matériaux sont métastables et d’une sensibilité déconcertante. Obtenir des couches minces exemptes de phases parasites est un travail de longue haleine. Ce défi a non-seulement été relevé, mais il a été possible de réaliser de la microfabrication sur les couches minces crues, rendant toute caractérisation des propriétés de transport beaucoup plus précise. L’ablation laser pulsée est la technique qui a été utilisée pour faire la croissance des couches minces étudiées. La diffraction des rayons-X a permis l’identification des phases de la structure cristalline, mais surtout l’étude des propriétés structurales des couches minces déposées. Une analyse des paramètres en plan (a) et hors plan (c) de la cellule unité de ces couches minces en fonction des conditions de croissance s’est avérée essentielle. Il a été remarqué que le paramètre hors plan joue un rôle limitant dans l’émergence de la supraconductivité. Des mesures de résistivité à très basses températures et sous champs magnétiques intenses ont permis d’établir un lien entre l’apparition de la supraconductivité et la grandeur du paramètre hors plan de la structure cristalline. Une transition complète ne semble être possible que lorsque le paramètre hors plan se trouve sous une grandeur critique, c = 3,41[A rond majuscule]. Des mesures d’effet Hall en fonction de la température sur des échantillons ayant différentes valeurs du paramètre hors plan ont permis de déterminer l’évolution des porteurs de charges présents en fonction de c. Les échantillons supraconducteurs suggèrent que la présence de trous comme porteurs de charge est essentielle à l’émergence de la supraconductivité. Leur présence semble diminuer rapidement à partir d’un paramètre hors plan plus grand que 3,41[A rond majuscule]. Il est possible d’établir un lien fondamental entre le comportement de la densité observé et celui d’une autre famille de supraconducteurs, les dopés aux électrons ayant une structure T’.

The present study deals with the French gerund and the Swedish syntactic correspondences in a parallel corpus. The analysis is based on 3,988 authentic instances of the gerund and their corresponding structures in Swedish texts. These are collected in a corpus consisting of 13 original contemporary French novels and 13 original contemporary Swedish novels, including their respective translations. The main purpose is to identify the Swedish corresponding structures and consider how, and to what extent, they transmit the integrative function and the adverbial interpretations of the French gerund.   Nine Swedish reoccurring structures are discerned, including the most common: coordinated clauses and adverbial clauses. The study shows that the nine Swedish structures share the integrative capacity of the gerund to different degrees, as well as how they transmit the adverbial interpretations in various ways. Some Swedish syntactic structures correlate with particular adverbial interpretation of the gerund. Another aim is to contribute to the existing research on the French gerund: the semantic analysis of the corpus has led to question – with authentic examples – the alleged absolute inability of the gerund to denote an eventuality that is the consequence of the eventuality denoted by the superordinate clause. The study also reveals, in light of Swedish corresponding structures, the relationship between certain adverbial interpretations of the gerund and more independent syntax in French.