Dissertations / Theses on the topic 'Timed automata'
To see the other types of publications on this topic, follow the link: Timed automata.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Timed automata.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Carlier, Pierre. "Verification of Stochastic Timed Automata." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLN058/document.
Full textAbstract:
La vérification est maintenant une branche très connue des sciences informatiques. Elle est cruciale lorsque l'on a affaire à des programmes informatiques dans des systèmes automatiques : on veut vérifier si un système donné est correct et s'il satisfait des propriétés nécessaires à son bon fonctionnement. Une façon d'analyser ces systèmes se fait par la modélisation mathématique. La question est alors : peut-on vérifier si le modèle satisfait les propriétés requises ? C'est ce que l'on appelle le problème du model-checking. Plusieurs modèles ont été étudiés dans la littérature. Nous portons notre intérêt sur des modèles qui peuvent mêler des aspects temporels et des aspects probabilistes. Dans cette thèse, nous étudions donc le modèle des automates temporisés et stochastiques (ATS). Les contributions de ce document sont divisées en deux parties. Tout d'abord, nous étudions les problèmes de model-checking qualitatifs et quantitatifs des ATS. Les ATS sont, en particulier, des systèmes probabilistes généraux et avec de tels modèles, on est intéressé par des questions du type : « Une propriété est-elle satisfaite, au sein d'un modèle donné, avec probabilité 1 ? » (qualitatif) ou bien « Peut-on calculer une approximation de la probabilité que le modèle satisfait une propriété donnée ? » (quantitatif).Nous étudions ces questions dans des systèmes probabilistes généraux en utilisant, entre autres, la notion de decisiveness utilisée dans les chaînes de Markov infinie dans le but d'obtenir d'importants résultats qualitatifs et que nous étendons ici dans notre contexte plus général. Nous prouvons plusieurs résultats pour les problèmes de model-checking qualitatifs et quantitatifs de ces systèmes probabilistes, certains d'entre eux étant des extensions de travaux antérieurs sur les chaînes de Markov, d'autres étant nouveaux, et nous montrons comment l'on peut appliquer ces résultats sur des sous-classes des ATS. Nous étudions ensuite la vérification compositionnelle des ATS. En général, un système est le résultat de plusieurs plus petits systèmes fonctionnant ensemble. La vérification compositionnelle permet alors de réduire l'analyse de gros systèmes aux analyses des plus petits systèmes qui le composent. Il est donc crucial d'avoir une bonne structure compositionnelle au sein des modèles mathématiques, et cela manque aux ATS. Dans cette thèse, nous définissons un opérateur de composition pour les ATS. Nous faisons d'abord l'hypothèse que les ATS composés fonctionnent complètement indépendamment l'un de l'autre, c'est-à-dire les ATS ne communiquent pas entre eux. Nous prouvons que notre définition satisfait bien cette hypothèse d'indépendance. Un tel opérateur de composition n'est pas très intéressant puisque, généralement, les systèmes interagissent entre eux. Mais c'est une première étape nécessaire. Nous introduisons donc le nouveau modèle des ATS interactifs (ATSI) qui vont permettre des interactions entre les systèmes. Nous définissons un opérateur de composition dans les ATSI qui va rendre possible des synchronisations entre les systèmes et qui est construit sur la précédente composition dans les ATS. Nous finissons cette thèse par l'identification d'une sous-classe de ATSI dans laquelle tous les résultats qualitatifs et quantitatifs fournis dans cette thèse peuvent être appliqués, et qui est donc accompagnée d'une bonne structure compositionnelle au sein du modèleVerification is now a well-known branch in computer science. It is crucial when dealing with computer programs in automatic systems: we want to check if a given system is correct and satisfies some specifications that should be met. One way to analyse those systems is to model them mathematically. The question is then: can we check if the model satisfies the required specifications ? This is called the model-checking problem. Several models have been studied in the literature. We have an interest for models that can mix both timing and randomized aspects. In this thesis we thus study the stochastic timed automaton model (STA). The contributions of this document are twofold. First, we study the qualitative and quantitative model-checking problems of STA. STA are, in particular, general probabilistic systems and with such model, one is thus interested in questions like « Is a property satisfied, within a given model, with probability 1 ? » (qualitative) or « Can we compute an approximation of the probability that the model satisfies a given property ? » (quantitative).We study those questions for general stochastic systems using, amongst other, the notion of decisiveness used in infinite Markov chains in order to get strong qualitative and quantitative results, and that we extend here in or more general context. We prove several results for the qualitative and quantitative model-checking problems of those probabilistic systems, some of them being extensions of previous work on Markov chains, others being new, and we show how it can be applied to subclasses of STA. Then we study the compositional verification in STA. In general, a system is the result of several smaller systems working together. Compositional verification allows then one to reduce the analysis of a big system to the analyses of the smaller systems which compose it. It is then crucial to have a good compositional framework in mathematical models, and this lacks in STA. In this thesis, we define an operator of composition for STA. We first make the assumption that the STA composed run completely independently from each other, i.e. they do not communicate between them. We prove that our definition satisfies indeed this independence assumption. Such an operator of composition is not very interesting as in general, systems do communicate. But it is a necessary first step. We then introduce the new model of interactive STA (ISTA) that will allow for interactions between the systems. We define an operator of composition in ISTA that will make synchronisations possible between the systems and that is built on the previous composition in STA. We end this thesis with the identification of a subclass of ISTA in which all the qualitative and quantitative results provided in this thesis can be applied, and which thus comes with the nice compositional framework defined in the model
2
Park, Young-Saeng. "Automatic schedule computation for distributed real-time systems using timed automata." Thesis, Northumbria University, 2008. http://nrl.northumbria.ac.uk/745/.
Full textAbstract:
The time-triggered architecture is becoming accepted as a means of implementing scalable, safer and more reliable solutions for distributed real-time systems. In such systems, the execution of distributed software components and the communication of messages between them take place in a fixed pattern and are scheduled in advance within a given scheduling round by a global scheduling policy. The principal obstacle in the design of time-triggered systems is the difficulty of finding the static schedule for all resources which satisfies constraints on the activities within the scheduling round, such as the meeting of deadlines. The scheduler has to consider not only the requirements on each processor but also the global requirements of system-wide behaviour including messages transmitted on networks. Finding an efficient way of building an appropriate global schedule for a given system is a major research challenge. This thesis proposes a novel approach to designing time-triggered schedules which is radically different from existing mathematical methods or algorithms for schedule generation. It entails the construction of timed automata to model the arrival and execution of software tasks and inter-task message communication for a system; the behaviour of an entire distributed system is thus a parallel composition of these timed automata models. A job comprises a sequence of tasks and messages; this expresses a system-wide transaction which may be distributed over a system of processors and networks. The job is formalized by a timed automata based on the principle that a task or message can be modelled by finite states and a clock variable. Temporal logic properties are formed to express constraints on the behaviour of the system components such as precedence relationships between tasks and messages and adherence to deadlines. Schedules are computed by formally verifying that these properties hold for an evolution of the system; a successful schedule is simply a trace generated by the verifier, in this case the UPPAAL model-checking tool has been employed to perform the behaviour verification. This approach guarantees to generate a practical schedule if one exists and will fail to construct any schedule if none exists. A prototype toolset has been developed to automate the proposed approach to create of timed automata models, undertake the analysis, extract schedules from traces and visualize the generated schedules. Two case studies, one of a cruise control system, the other a manufacturing cell system, are presented to demonstrate the applicability and usability of the approach and the application of the toolset. Finally, further constraints are considered in order to yield schedules with limited jitter, increased efficiency and system-wide properties.
3
Amnell, Tobias. "Code synthesis for timed automata." Licentiate thesis, Uppsala universitet, Avdelningen för datorteknik, 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-86154.
Full textAbstract:
In this thesis, we study executable behaviours of timed models. The focus is on synthesis of executable code with predictable behaviours from high level abstract models. We assume that a timed system consists of two parts: the control software and the plant (i.e. the environment to be controlled). Both are modelled as timed automata extended with real time tasks. We consider the extended timed automata as design models. We present a compilation procedure to transform design models to executable code including a run-time scheduler (run time system) preserving the correctness and schedulability of the models. The compilation procedure has been implemented in a prototype C-code generator for the brickOS operating system included in the Times tool. We also present an animator, based on hybrid automata, to be used to describe a simulated environment (i.e. the plant) for timed systems. The tasks of the hybrid automata define differential equations and the animator uses a differential equations solver to calculate step-wise approximations of real valued variables. The animated objects, described as hybrid automata, are compiled by the Times tool into executable code using a similar procedure as for controller software. To demonstrate the applicability of timed automata with tasks as a design language we have developed the control software for a production cell. The production cell is built in LEGO and is controlled by a Hitachi H8 based LEGO-Mindstorms control brick. The control software has been analysed (using the Times tool) for schedulability and other safety properties. Using results from the analysis we were able to avoid generating code for parts of the design that could never be reached, and could also limit the amount of memory allocated for the task queue.
4
Trivedi, Ashutosh. "Competative optimisation on timed automata." Thesis, University of Warwick, 2009. http://wrap.warwick.ac.uk/2243/.
Full textAbstract:
Timed automata are finite automata accompanied by a finite set of real-valued variables called clocks. Optimisation problems on timed automata are fundamental to the verification of properties of real-time systems modelled as timed automata, while the control-program synthesis problem of such systems can be modelled as a two-player game. This thesis presents a study of optimisation problems and two-player games on timed automata under a general heading of competitive optimisation on timed automata. This thesis views competitive optimisation on timed automata as a multi-stage decision process, where one or two players are confronted with the problem of choosing a sequence of timed moves—a time delay and an action—in order to optimise their objectives. A solution of such problems consists of the “optimal” value of the objective and an “optimal” strategy for each player. This thesis introduces a novel class of strategies, called boundary strategies, that suggest to a player a symbolic timed move of the form (b, c, a)— “wait until the value of the clock c is in very close proximity of the integer b, and then execute a transition labelled with the action a”. A distinctive feature of the competitive optimisation problems discussed in this thesis is the existence of optimal boundary strategies. Surprisingly perhaps, many competitive optimisation problems on timed automata of practical interest admit optimal boundary strategies. For example, optimisation problems with reachability price, discounted price, and average-price objectives, and two-player turn-based games with reachability time and average time objectives. The existence of optimal boundary strategies allows one to work with a novel abstraction of timed automata, called a boundary region graph, where players can use only boundary strategies. An interesting property of a boundary region graph is that, for every state, the set of reachable states is finite. Hence, the existence of optimal boundary strategies permits us to reduce competitive optimisation problem on a timed automaton to the corresponding competitive optimisation problem on a finite graph.
5
Sankur, Ocan. "Robustness in timed automata : analysis, synthesis, implementation." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2013. http://tel.archives-ouvertes.fr/tel-00910333.
Full textAbstract:
Timed automata are a formalism to model, verify, and synthesize real-time systems. They have the advantage of having an abstract mathematical semantics, which allow formalizing and solving several verification and synthesis problems. However, timed automata are intended to design models, rather than completely describe real systems. Therefore, once the design phase is over, it remains to check whether the behavior of an actual implementation corresponds to that of the timed automaton model. An important step before implementing a system design is ensuring its robustness. This thesis considers a notion of robustness that asks whether the behavior of a given timed automaton is preserved, or can be made so, when it is subject to small perturbations. Several approaches are considered: Robustness analysis seeks to decide whether a given timed automaton tolerates perturbations, and in that case to compute the (maximum) amount of tolerated perturbations. In robust synthesis, a given system needs to be controlled by a law (or strategy) which tolerates perturbations upto some computable amount. In robust implementation, one seeks to automatically transform a given timed automaton model so that it tolerates perturbations by construction. Several perturbation models are considered, ranging from introducing error in time measures (guard enlargement), forbidding behaviors that are too close to boundaries (guard shrinking), and restricting the time domain to a discrete sampling. We also formalize robust synthesis problems as games, where the control law plays against the environment which can systematically perturb the chosen moves, by some bounded amount. These problems are studied on timed automata and their variants, namely, timed games, and weighted timed automata and games. Algorithms for the parameterized robustness analysis against guard enlargements, and guard shrinkings are presented. The robust synthesis problem is studied for two variants of the game semantics, for timed automata, games, and their weighted extensions. A software tool for robustness analysis against guard shrinkings is presented, and experimental results are discussed. The robust implementation problem is also studied in two different settings. In all algorithms, an upper bound on perturbations that the given timed automaton tolerates can be computed.
6
Ericsson, Ann-Marie. "Deriving ECA-rules from timed-automata specifications." Thesis, University of Skövde, Department of Computer Science, 2002. http://urn.kb.se/resolve?urn=urn:nbn:se:his:diva-655.
Full textAbstract:
Real-time systems are required to answer to external stimuli within a specified time-period. For this to be possible, the systems behaviour must be predictable. The use of active databases in real-time systems introduces unpredictability in the system, e.g. due to their use of active rules. The behaviour in active databases is usually specified in ECA-rules. Sets of ECA-rules are hard to analyse, which implies that the behaviour of the ECA-rule set is hard to predict.
The purpose of this project is to evaluate the ability to support the development of a predictable ECA-rule set. Using a formal method for the specification task is desirable, since a formal specification is analysable and can be proven correct. In this project, timed-automata are used for specifying the systems behaviour. A method for deriving predictable ECA-rules from a timed-automaton specification is developed, and successfully applied on a case-study specification. For this case-study specification, a set of ECA-rules preserving the analysed behaviour of the timed-automata specification is derived.
7
Nehme, Carl 1981. "The VAT tool : automatic transformation of VHDL to timed automata." Thesis, Massachusetts Institute of Technology, 2004. http://hdl.handle.net/1721.1/17790.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2004.Includes bibliographical references (leaves 61-66).
Embedded systems have become an integral part of the systems we use today. These types of systems are constrained by both stringent time requirements and limited resource availability. Traditionally, high-integrity embedded systems operated on well understood hardware platforms. The emergence of inexpensive FPGAs (Field Programmable Gate Arrays) and ASICs (Application Specific Integrated Circuits) as operational platforms for embedded software, has resulted in the system developer having to verify both the hardware and the software components. The stringent processes used over the system development lifecycle have to be augmented to account for this paradigm shift. One possible approach is to create a homogenous formal model that accounts for both the hardware and the software components of the system. This thesis focuses on making a contribution to the extraction of formal models from the VHDL specification of the operational platform. The research underlying this thesis was driven by the goals of: a) augmenting the system developer's verification and validation toolbox with a powerful yet easy-to-use tool; b) developing a tool that is modular, extensible, and adaptable to changing customer requirements; c) providing a transparent transformation process, which can be leveraged by both academia and industry. The thesis discusses in detail, the design and development of the VAT tool, that transforms VHDL specifications into finite state machines. It discusses the use of model checking on the extracted formal model and presents a visualization technique that enables manual inspection of the formal model.
by Carl Nehme.
S.M.
8
Hagman, Mikael. "Instrumentation of timed automata for formal verification of timed properties." Thesis, Linköping University, Department of Computer and Information Science, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-9861.
Full textAbstract:
Embedded systems are used in many technical products of today. The tendency also points to the fact that they are in many ways becoming more and more complex as technology advances. Systems like advanced avionics, air bags, ABS brakes or any real-time embedded system requires reliability, correctness and timeliness. This puts hard pressure on designers, analyzers and developers. The need for high performance and non failing systems has therefore led to a growing interest in modeling and verification of component-based embedded systems in order to reduce costs and simplify design and development. The solution proposed by the Embedded Systems Lab at Linköping University is the modeling language PRES+, Petri Net based Representation for Embedded Systems.
PRES+ models are then translated into timed automata, TA, which is used by the UPPAAL verification tool. To be able to verify timing properties the translated TA model must be instrumented with certain timers, called clocks. These clocks must be reset in a manner reflected by the property to be verified.
This thesis will provide a solution to the problem and also give the reader necessary information in order to understand the theoretical background needed. The thesis will also show the reader the importance of modeling and time verification in the development of embedded systems. A simple example is used to describe and visualize the benefit regarding real-time embedded systems as well as the importance of the ability to verify these systems.
The conclusion drawn stresses the fact that high development costs, possible gain of human lives and the problems in developing complex systems only emphasize the need for easy to handle and intuitive verification methods.
9
Mavrommatis, Panayiotis P. "Simulation of timed input/output automata." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/36395.
Full textAbstract:
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Includes bibliographical references (p. 73-74).
This Master of Engineering Thesis describes the design, implementation, and usage of the TIOA Simulator. The TIOA Simulator, along with the other components of the TIOA Toolset aims to provide a framework for developing dependable distributed systems. The project is based on the Timed Input/Output Automaton framework, and supports TIOA, a formal language for specifying timed I/O automata. Simulation of TIOA programs is useful in the process of testing the proposed system over a specific set of executions. During the execution the Simulator is able to test proposed invariants and validate a proposed simulation relation between the system's implementation and its specification. A step correspondence between the steps of the implementation and the specification drives the validation of the simulation relation. The identification and validation of the invariants and the simulation relation constitutes the first step towards a formal verification of the system's correctness. The proposed step correspondence can be used in a formal proof to show that the proposed relation is indeed a simulation relation.
by Panayiotis P. Mavrommatis.
M.Eng.
10
Widerberg, Ernst. "A Modeling Language for Timed Automata." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-291554.
Full textAbstract:
This work details the design and implementation of a modeling language for timed automata. The primary intended use of the language TML is as an interface to controller synthesis system m2mc, which is being developed in a current KTH/Chalmers research project. TML is evaluated by a qualitative comparison with the modeling languages of two well-known model checking tools: Uppaal and Kronos. Two example systems (Fischer’s mutual exclusion protocol and CSMA/CD) are implemented in all three languages, to discover the relative merits of each language. Although not as feature rich as Uppaal, TML brings some new language features which are found to be potentially useful for modeling timed automata systems. These features are largely adopted from the general graph description language Dot, used by programs in the Graphviz software package. As m2mc is still in early development and liable to change, an intermediate JSON representation for timed automata is defined. A compiler targeting this intermediate representation is implemented using Miking, a new compiler tool under development in a separate KTH project. Further compilation from JSON to Uppaal is implemented as a proof of concept.Detta arbete behandlar utformning och implementering av ett modelleringsspråk för tidsautomater. Språket TML:s huvudsakliga tänkta tillämpning är att fungera som ett användargränssnitt för kontrollsyntessystemet m2mc, vilket utvecklas i ett pågående forskningsprojekt på KTH och Chalmers. TML utvärderas genom en kvalitativ jämförelse med modelleringsspråken för två välkända model checking-verktyg: Uppaal och Kronos. Två exempelsystem (Fischers protokoll för mutual exclusion och CSMA/CD) implementeras i vardera modelleringsspråk för att undersöka de olika språkens relativa fördelar och nackdelar. Fastän TML inte är lika omfattande i funktionalitet som Uppaal så bidrar språket med en del nya funktioner, vilka baserat på utvärderingen anses kunna vara användbara för modellering av tidsautomatsystem. Dessa funktioner hämtas till stor del från språket Dot, vilket används i mjukvarupaketet Graphviz för att modellera generella grafer. Eftersom m2mc är i tidig utveckling vore direkt integration med TML inte praktiskt användbart. Därför definieras istället ett mellanformat för tidsautomater i JSON. En kompilator för TML som producerar detta mellanformat implementeras med användning av Miking, ett nytt kompilatorverktyg under utveckling i ett separat KTH-projekt. Som ett koncepttest implementeras vidare kompilering från JSON till Uppaal.
11
Ramadian, Yusi. "Parametric Real-Time System Feasibility Analysis Using Parametric Timed Automata." Doctoral thesis, Università degli studi di Trento, 2012. https://hdl.handle.net/11572/368709.
Full textAbstract:
Real-time applications are playing an increasingly significant role in our life. The cost and risk involved
in their design leads to the need for a correct and robust modelling of the system before its deployment.
Many approaches have been proposed to verify the schedulability of real-time task system. A frequent
limitation is that they force the task activation to restrictive patterns (e.g. periodic). Furthermore, the
type of analysis carried out by the real-time scheduling theory relies on restrictive assumptions that
could make the designers miss important optimization opportunities. On the other hand, the application
of formal methods for verification of timed systems typically produces a yes/no answer that does not
suggest any correction action or robustness margins of a given design.
This work proposes an approach to combine the benefits of formal method in terms of flexibility with
the production of a clear feedback for the designers. The key idea is to use parametric timed automata
to enable the definition of flexible task activation patterns. The Parametric Verification of Temporal
Properties (PTVP) algorithm proposed in this work produces a region of feasible parameters for realtime
system. All the parameter valuation within this region is guaranteed to make the system respect
the desired temporal behaviour. In this way developers are provided with a richer information than the
simple feasibility of a given design choice.
This method uses symbolic model checking technique to produce the result that is a union of polyhedral
regions in the parameter space associated with feasible parameters. It is implemented in the tool
Quinq that is based on NuSMV3. The tool also implemented an optimization to speed up the search,
such as using non-parametric model checker to find counterexamples (i.e. traces) related to the unfeasible
choices of parameters.
Two applications of the tool and of the underlying method to several real-time system examples are
presented in this dissertation : periodic real-time system tasks with offset and heterogeneous distributed
real-time systems. A work that applies the tool in collaboration with another real-time system analysis
tool, Modular Performance Analysis Toolbox, is also presented to show one of the many possible
application of the method presented in this work.
In this work we also compare our approach to the state of the art in the field of sensitivity analysis
of real-time systems. However, compared to the other tools and approaches in this field, the method
offered in this work presents unique advantages in the generality of the system modelling approach and
the possibility to analyse the entire region of feasibility of any desired parameter in the system.
12
Ramadian, Yusi. "Parametric Real-Time System Feasibility Analysis Using Parametric Timed Automata." Doctoral thesis, University of Trento, 2012. http://eprints-phd.biblio.unitn.it/763/1/Dissertation.pdf.
Full textAbstract:
Real-time applications are playing an increasingly significant role in our life. The cost and risk involved
in their design leads to the need for a correct and robust modelling of the system before its deployment.
Many approaches have been proposed to verify the schedulability of real-time task system. A frequent
limitation is that they force the task activation to restrictive patterns (e.g. periodic). Furthermore, the
type of analysis carried out by the real-time scheduling theory relies on restrictive assumptions that
could make the designers miss important optimization opportunities. On the other hand, the application
of formal methods for verification of timed systems typically produces a yes/no answer that does not
suggest any correction action or robustness margins of a given design.
This work proposes an approach to combine the benefits of formal method in terms of flexibility with
the production of a clear feedback for the designers. The key idea is to use parametric timed automata
to enable the definition of flexible task activation patterns. The Parametric Verification of Temporal
Properties (PTVP) algorithm proposed in this work produces a region of feasible parameters for realtime
system. All the parameter valuation within this region is guaranteed to make the system respect
the desired temporal behaviour. In this way developers are provided with a richer information than the
simple feasibility of a given design choice.
This method uses symbolic model checking technique to produce the result that is a union of polyhedral
regions in the parameter space associated with feasible parameters. It is implemented in the tool
Quinq that is based on NuSMV3. The tool also implemented an optimization to speed up the search,
such as using non-parametric model checker to find counterexamples (i.e. traces) related to the unfeasible
choices of parameters.
Two applications of the tool and of the underlying method to several real-time system examples are
presented in this dissertation : periodic real-time system tasks with offset and heterogeneous distributed
real-time systems. A work that applies the tool in collaboration with another real-time system analysis
tool, Modular Performance Analysis Toolbox, is also presented to show one of the many possible
application of the method presented in this work.
In this work we also compare our approach to the state of the art in the field of sensitivity analysis
of real-time systems. However, compared to the other tools and approaches in this field, the method
offered in this work presents unique advantages in the generality of the system modelling approach and
the possibility to analyse the entire region of feasibility of any desired parameter in the system.
13
Nolte, Tina Ann 1979. "Virtual stationary timed automata for mobile networks." Thesis, Massachusetts Institute of Technology, 2009. http://hdl.handle.net/1721.1/47745.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.Includes bibliographical references (p. 339-347).
In this thesis, we formally define a programming abstraction for mobile networks called the Virtual Stationary Automata programming layer, consisting of real mobile clients, virtual timed I/O automata called virtual stationary automata (VSAs), and a communication service connecting VSAs and client nodes. The VSAs are located at prespecified regions that tile the plane, defining a static virtual infrastructure. We present a theory of self-stabilizing emulation and use this theory to prove correct a self-stabilizing algorithm to emulate a timed VSA using the real mobile nodes that are currently residing in the VSA's region. We also specify two important services for mobile networks: motion coordination and end-to-end routing. We split the implementation of the end-to-end routing service into three smaller pieces, consisting of geographic routing and location management services with an end-to-end routing service built on top of them. We provide stabilizing implementations of each of these services using the VSA abstraction, and provide formal correctness analyses for each implementation.
by Tina Ann Nolte.
Ph.D.
14
Nguyen, Hoang Gia. "Efficient Parametric Verification of Parametric Timed Automata." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCD038.
Full textAbstract:
Les systèmes temps-réel critiques deviennent de plus en plus ubiquitaires et jouent un rôle majeur de nos jours. Pour garantir le bon comportement d’un système, leur correction doit être vérifiée avant les mises en service opérationnel. Outre la vérification fonctionnelle, la vérification du comportement temporel est également cruciale. Les tech niques de vérification garantissent que les systèmes logiciels ou matériels satisfont les contraintes attendues. La plupart des méthodes de vérification formelle pour les systèmes temporisés garantissent leur correction pour des valeurs prédéfinies des contraintes temporelles, mais pas pour d’autres valeurs non définies a priori, dues par exemple à un changement de l’environnement, et qui peuvent conduire à des comportements du système non désirés. Malheureusement, la vérification de tels systèmes pour différentes valeurs temporelles peut être un obstacle et coûteuse en temps. Ainsi, en s’abstrayant de valeurs temporelles spécifiques à l’aide de paramètres, de nombreuses valeurs temporelles d’un système peuvent être synthétisées et vérifiées simultanément : cette technique est la synthèse de paramètres. Les techniques de synthèse de paramètres constituent un défi majeur pour la vérification. Elles souffrent du problème de l’explosion combinatoire de l’espace d’´états, c’est-a`-dire de la génération d’un nombre d’´états considérable lors de la vérification formelle du système. Dans un premier temps, nous nous sommes intéressés à tirer parti des spécificités des architectures informatiques distribuées modernes. Ainsi, les algorithmes de synthèse de paramètres ont dû être redéfinis et adaptés au cas distribué. Nous proposons dans cette thèse différents schémas de distribution pour accélérer les procédures de synthèse de paramètres. Nous nous intéressons également à l’étude de techniques telles que la vérification symbolique, la subsomption, etc. et à leur impact sur l’explosion de l’espace d’états. Nous introduisons donc ensuite plusieurs heuristiques d’exploration afin de réduire l’explosion de l’espace d’états. Celles-ci sont intégrées a` nos nouveaux algorithmes de synthèse de paramètres. L’un de ces algorithmes est étendu de manière distribuée, conduisant `a des performances spectaculaires dans nos expérimentations. Enfin, pour obtenir un résultat réalisable, nous présentons une approche qui détecte des systèmes temporisés effectuant un nombre infini d’actions en un temps fini, connu sous le nom de phénomène Zeno. En pratique, de tels comportements ne peuvent pas avoir lieu, et ne constituent pas des contre-exemples effectifs. De plus, nous proposons une approche distribuée pour détecter des phénomènes non Zeno à large échelle. Nous introduisons un algorithme détectant des comportements non Zeno, ainsi que sa version distribuée. Au moment de l’écriture de cette thèse, ceci constitue les premiers résultats sur la synthèse de paramètres non ZenoCritical real-time systems are becoming ubiquitous and are playing a vital role in our world. To provide guarantees that the system is behaving correctly, the correctness of these systems need to be verified before running. Besides functional checking, the timed behavior checking is also crucial. Indeed, the correctness of the systems also depends on the timing values or delays of internal operations that can be affected by the environment. Verification techniques assure that software or hardware systems fully satisfy all their expected requirements. Most formal verification methods for timed systems guarantee the correctness of a timed system for the predefined timing values in its blueprint, but not for other undefined timing values which might occur by the environment change and lead to undesired system behaviors. Unfortunately, verifying such system for various timing values can be an obstacle and time-consuming. Therefore, by abstracting these specific timing values with parameters, many timing values of a system can be easily synthesized and checked at the same time : this technique is also known as parameter synthesis. As a huge challenge for the verification, parameter synthesis techniques also suffer from the “state space explosion” problem, which is the explosion of the number of possible states while verifying a system formally. Firstofall, we are interested in taking advantage of the capabilities of current distributed architectures, and parameter synthesis algorithms should be redefined and adapted to the distributed case. We propose in the thesis several distribution schemes that can accelerate our parameter synthesis procedures. We also focus on studying the techniques such as symbolic verification, zone subsumption, etc. and how they affect the state space explosion problem. Then we introduce several smart state exploration techniques with some heuristics, in order to reduce the state space explosion. These techniques and heuristics are integrated into our new synthesis algorithms, and one of these algorithms is also extended in a distributed manner which gives an impressive performance in our benchmarks. Furthermore, to achieve a reliable result we present an approach for detecting timed systems doing an infinite amount of actions in a finite time, which is known as the Zeno phenomenon in theory. In reality, it is infeasible and such counterexamples should always be avoided. Additionally, to detect the non-Zeno phenomenon on a large scale network model, we also distribute our approach on clusters. In the end, we introduce an algorithm to detect non-Zeno runs and its distributed version of it for large-scale models. At the time of writing this thesis, this is also the first work on non-Zeno parameter synthesis
15
Tran, Thanh tung. "Verification of timed automata : reachability, liveness and modelling." Thesis, Bordeaux, 2016. http://www.theses.fr/2016BORD0168/document.
Full textAbstract:
Cette thèse revisite les algorithmes standards pour les problèmes d'accessibilité et de vivacité des automates temporisés. L'algorithme standard pour tester l'accessibilité consiste à utiliser l'inclusion de zones pour explorer efficacement un arbre de recherche abstrait. Cependant, l'ordre du parcours du graphe a une forte incidence sur l'efficacité de l'algorithme. Dans cette thèse nous introduisons deux stratégies, nommées ranking et waiting, et une combinaison des deux. De nombreux exemples montrent que la combinaison des deux stratégies aide l'algorithme d'accessibilité à éviter des explorations non nécessaires. Le problème de vivacité est couramment vérifiées par l'analyse des cycles dans l'automate temporisé. Contrairement à l'algorithme d'accessibilité, l'algorithme pour l'analyse de vivacité ne peut pas librement utiliser l'inclusion de zones. Par conséquent, il y a des situations où l'algorithme doit faire une longue exploration avant de conclure l'existence d'un cycle. Nous proposons une analyse accélérée des cycles, nommées w-iterability checking, qui permet d'améliorer la performance de l'algorithme de vivacité des automates temporisés. En plus, nous proposons une modélisation du mécanisme de démarrage du protocole FlexRay. La modélisation permet à vérifier le mécanisme dans configurations différents du réseau FlexRay. Nous présentons également un outil de visualisation qui aide à mieux comprendre le fonctionnement des algorithmes d'analyseThis thesis revisits the standard algorithms for reachability and liveness analysis of timed automata. The standard algorithm for reachability analysis consists in using zone inclusion to efficiently explore a finite abstract zone graph of a timed automaton. It has been observed that the search order may strongly affect the performance of the algorithm. For the same algorithm, one search order may introduce a lot more exploration than another. In order to deal with the search order problem, we propose two strategies, named ranking strategy and waiting strategy, and a combination of the two. We show on a number of examples, the combining strategy helps to reduce unnecessary exploration in the standard algorithms. The standard algorithm for liveness analysis consists in looking for reachability of cycles in timed automata. But unlike the algorithm for safety analysis, the algorithm for liveness analysis cannot freely use zone inclusion. Consequently, there are situations where the algorithm has to perform a long exploration before reporting the result. In this thesis, we propose an accelerated checking for cycles in timed automata, named !-iterability checking, to improve the performance of the state-of-the-art algorithm for liveness analysis of timed automata. Furthermore, we present a new model for the startup procedure of FlexRay. The model allows to verify the procedure on different configurations of FlexRay networks. It also allows to evaluate the performance of our new strategies for safety analysis of timed automata. In addition, we present a methodology that uses visualization tools to get more insights into the execution of the algorithms
16
Renard, Matthieu. "Runtime Enforcement of (Timed) Properties with Uncontrollable Events." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0833/document.
Full textAbstract:
Cette thèse étudie l’enforcement de propriétés temporisées à l’exécution en présence d’évènements incontrôlables. Les travaux se placent dans le cadre plus général de la vérification à l’exécution qui vise à surveiller l’exécution d’un système afin de s’assurer qu’elle respecte certaines propriétés. Ces propriétés peuvent être spécifiées à l’aide de formules logiques, ou au moyen d’autres modèles formels, parfois équivalents, comme des automates. Nous nous intéressons à l’enforcement à l’exécution de propriétés spécifiées par des automates temporisés. Tout comme la vérification à l’exécution, l’enforcement à l’exécution surveille l’exécution d’un système, la différence étant qu’un mécanisme d’enforcement réalise certaines modifications sur l’exécution afin de la contraindre à satisfaire la propriété souhaitée. Nous étudions plus particulièrement l’enforcement à l’exécution lorsque certains évènements de l’exécution sont incontrôlables, c’est-à-dire qu’ils ne peuvent pas être modifiés par un mécanisme d’enforcement. Nous définissons des algorithmes de synthèse de mécanismes d’enforcement décrits de manières fonctionnelle puis opérationnelle, à partir de propriétés temporisées régulières (pouvant être représentées par des automates temporisés). Ainsi, deux mécanismes d’enforcement équivalents sont définis, le premier présentant une approche correcte sans considération d’implémentation, alors que le second utilise une approche basée sur la théorie des jeux permettant de précalculer certains comportements, ce qui permet de meilleures performances. Une implémentation utilisant ce précalcul est également présentée et évaluée. Les résultats sont encourageant quant à la faisabilité de l’enforcement à l’exécution en temps réel, avec des temps supplémentaires suffisamment courts sur de petites propriétés pour permettre une utilisation de tels systèmesThis thesis studies the runtime enforcement of timed properties when some events are uncontrollable. This work falls in the domain of runtime verification, which includes all the techniques and tools based on or related to the monitoring of system executions with respect to requirement properties. These properties can be specified using different models such as logic formulae or automata. We consider timed regular properties, that can be represented by timed automata. As for runtime verification, a runtime enforcement mechanism watches the executions of a system, but instead of just outputting a verdict, it modifies the execution so that it satisfies the property. We are interested in runtime enforcement with uncontrollable events. An uncontrollable event is an event that an enforcement mechanism can not modify. We describe the synthesis of enforcement mechanisms, in both a functional and an operational way, that enforce some desired timed regular property. We define two equivalent enforcement mechanisms, the first one being simple, without considering complexity aspects, whereas the second one has a better time complexity thanks to the use of game theory; the latter being better suited for implementation. We also detail a tool that implements the second enforcement mechanism, as well as some performance considerations. The overhead introduced by the use of our tool seems low enough to be used in some real-time application scenarios
17
D'Argenio, Pedro Ruben. "Algebras and automata for timed and stochastic systems." Enscheded : [s.n.], 1999. http://www.cs.famaf.unc.edu.ar/~dargenio/Publications/dissertation/dissertation.pdf.
Full text
18
De, Wulf Martin. "From timed models to timed implementations." Doctoral thesis, Universite Libre de Bruxelles, 2006. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210797.
Full textAbstract:
Computer Science is currently facing a grand challenge :finding good design practices for embedded systems. Embedded systems are essentially computers interacting with some physical process. You could find one in a braking systems or in a nuclear power plant for example. They present several design difficulties :first they are reactive systems, interacting indefinitely with their environment. Second,they must satisfy real-time constraints specifying when they should respond, and not only how. Finally, their environment is often deeply continuous, presenting complex dynamics. The formal models of choice for specifying such systems are timed and hybrid automata for which model checking is pretty well studied.
In a first part of this thesis, we study a complete design approach, including verification and code generation, for timed automata. We have to define a new semantics for timed automata, the AASAP semantics, that preserves the decidability properties for model checking and at the same time is implementable. Our notion of implementability is completely novel, and relies on the simulation of a semantics that is obviously implementable on a real platform. We wrote tools for the analysis and code generation and exemplify them on a case study about the well known Philips Audio Control Protocol.
In a second part of this thesis, we study the problem of controller synthesis for an environment specified as a hybrid automaton. We give a new solution for discrete controllers having only an imperfect information about the state of the system. In the process, we defined a new algorithm, based on the monotonicity of the controllable predecessors operator, for efficiently finding a controller and we show some promising applications on a classical problem :the universality test for finite automata.
Doctorat en sciences, Spécialisation Informatique
info:eu-repo/semantics/nonPublished
19
Quaas, Karin. "Kleene-Schützenberger and Büchi Theorems for Weighted Timed Automata." Doctoral thesis, Universitätsbibliothek Leipzig, 2010. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-38791.
Full textAbstract:
In 1994, Alur and Dill introduced timed automata as a simple mathematical model for modelling the behaviour of real-time systems.
In this thesis, we extend timed automata with weights. More detailed, we equip both the states and transitions of a timed automaton with weights taken from an appropriate mathematical structure. The weight of a transition determines the weight for taking this transition, and the weight of a state determines the weight for letting time elapse in this state. Since the weight for staying in a state depends on time, this model, called weighted timed automata, has many interesting applications, for instance, in operations research and scheduling. We give characterizations for the behaviours of weighted timed automata in terms of rational expressions and logical formulas. These formalisms are useful for the specification of real-time systems with continuous resource consumption. We further investigate the relation between the behaviours of weighted timed automata and timed automata. Finally, we present important decidability results for weighted timed automata.
20
Grinchtein, Olga. "Learning of Timed Systems." Doctoral thesis, Uppsala University, Department of Information Technology, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-8763.
Full textAbstract:
Regular inference is a research direction in machine learning. The goal of regular inference is to construct a representation of a regular language in the form of deterministic finite automaton (DFA) based on the set of positive and negative examples. DFAs take strings of symbols (words) as input, and produce a binary classification as output, indicating whether the word belongs to the language or not. There are two types of learning algorithms for DFAs: passive and active learning algorithms. In passive learning, the set of positive and negative examples is given and not chosen by inference algorithm. In contrast, in active learning, the learning algorithm chooses examples from which a model is constructed.
Active learning was introduced in 1987 by Dana Angluin. She presented the L* algorithm for learning DFAs by asking membership and equivalence queries to a teacher who knows the regular language accepted by DFA to be learned. A membership query checks whether a word belongs to the language or not. An equivalence query checks whether a hypothesized model is equivalent to the DFA to be learned.The L* algorithm has been found to be useful in different areas, including black box checking, compositional verification and integration testing. There are also other algorithms similar to L* for regular inference. However, the learning of timed systems has not been studied before. This thesis presents algorithms for learning timed systems in an active learning framework.
As a model of timed system we choose event-recording automata (ERAs), a determinizable subclass of the widely used timed automata. The advantages of ERA in comparison with timed automata, is that it is known priori the set of clocks of an ERA and when clocks are reset. The contribution of this thesis is four algorithms for learning deterministic event-recording automaton (DERA). Two algorithms learn a subclass of DERA, called event-deterministic ERA (EDERA) and two algorithms learn general DERA.
The problem with DERAs that they do not have canonical form. Therefore we focus on subclass of DERAs that have canonical representation, EDERA, and apply the L* algorithm to learn EDERAs. The L* algorithm in timed setting requires a procedure that learns clock guards of DERAs. This approach constructs EDERAs which are exponentially bigger than automaton to be learned. Another procedure can be used to lean smaller EDERAs, but it requires to solve NP-hard problem.
We also use the L* algorithm to learn general DERA. One drawback of this approach that inferred DERAs have a form of region graph and there is blow-up in the number of transitions. Therefore we introduce an algorithm for learning DERA which uses a new data structure for organising results of queries, called a timed decision tree, and avoids region graph construction. Theoretically this algorithm can construct bigger DERA than the L* algorithm, but in the average case we expect better performance.
21
Neumann, Stefan, and Holger Giese. "Scalable compatibility for embedded real-time components via language progressive timed automata." Universität Potsdam, 2013. http://opus.kobv.de/ubp/volltexte/2013/6385/.
Full textAbstract:
The proper composition of independently developed components of an embedded real- time system is complicated due to the fact that besides the functional behavior also the non-functional properties and in particular the timing have to be compatible. Nowadays related compatibility problems have to be addressed in a cumbersome integration and configuration phase at the end of the development process, that in the worst case may fail. Therefore, a number of formal approaches have been developed, which try to guide the upfront decomposition of the embedded real-time system into components such that integration problems related to timing properties can be excluded and that suitable configurations can be found. However, the proposed solutions require a number of strong assumptions that can be hardly fulfilled or the required analysis does not scale well. In this paper, we present an approach based on timed automata that can provide the required guarantees for the later integration without strong assumptions, which are difficult to match in practice. The approach provides a modular reasoning scheme that permits to establish the required guarantees for the integration employing only local checks, which therefore also scales. It is also possible to determine potential configuration settings by means of timed game synthesis.Die korrekte Komposition individuell entwickelter Komponenten von eingebetteten Realzeitsystemen ist eine Herausforderung, da neben funktionalen Eigenschaften auch nicht funktionale Eigenschaften berücksichtigt werden müssen. Ein Beispiel hierfür ist die Kompatibilität von Realzeiteigenschaften, welche eine entscheidende Rolle in eingebetteten Systemen spielen. Heutzutage wird die Kompatibilität derartiger Eigenschaften in einer aufwändigen Integrations- und Konfigurationstests am Ende des Entwicklungsprozesses geprüft, wobei diese Tests im schlechtesten Fall fehlschlagen. Aus diesem Grund wurde eine Zahl an formalen Verfahren Entwickelt, welche eine frühzeitige Analyse von Realzeiteigenschaften von Komponenten erlauben, sodass Inkompatibilitäten von Realzeiteigenschaften in späteren Phasen ausgeschlossen werden können. Existierenden Verfahren verlangen jedoch, dass eine Reihe von Bedingungen erfüllt sein muss, welche von realen Systemen nur schwer zu erfüllen sind, oder aber, die verwendeten Analyseverfahren skalieren nicht für größere Systeme. In dieser Arbeit wird ein Ansatz vorgestellt, welcher auf dem formalen Modell des Timed Automaton basiert und der keine Bedingungen verlangt, die von einem realen System nur schwer erfüllt werden können. Der in dieser Arbeit vorgestellte Ansatz enthält ein Framework, welches eine modulare Analyse erlaubt, bei der ausschließlich miteinender kommunizierende Komponenten paarweise überprüft werden müssen. Somit wird eine skalierbare Analyse von Realzeiteigenschaften ermöglicht, die keine Bedingungen verlangt, welche nur bedingt von realen Systemen erfüllt werden können.
22
Abou, Trab Mohammad. "Software engineering : testing real-time embedded systems using timed automata based approaches." Thesis, Brunel University, 2012. http://bura.brunel.ac.uk/handle/2438/6611.
Full textAbstract:
Real-time Embedded Systems (RTESs) have an increasing role in controlling society infrastructures that we use on a day-to-day basis. RTES behaviour is not based solely on the interactions it might have with its surrounding environment, but also on the timing requirements it induces. As a result, ensuring that an RTES behaves correctly is non-trivial, especially after adding time as a new dimension to the complexity of the testing process. This research addresses the problem of testing RTESs from Timed Automata (TA) specification by the following. First, a new Priority-based Approach (PA) for testing RTES modelled formally as UPPAAL timed automata (TA variant) is introduced. Test cases generated according to a proposed timed adequacy criterion (clock region coverage) are divided into three sets of priorities, namely boundary, out-boundary and in-boundary. The selection of which set is most appropriate for a System Under Test (SUT) can be decided by the tester according to the system type, time specified for the testing process and its budget. Second, PA is validated in comparison with four well-known timed testing approaches based on TA using Specification Mutation Analysis (SMA). To enable the validation, a set of timed and functional mutation operators based on TA is introduced. Three case studies are used to run SMA. The effectiveness of timed testing approaches are determined and contrasted according to the mutation score which shows that our PA achieves high mutation adequacy score compared with others. Third, to enhance the applicability of PA, a new testing tool (GeTeX) that deploys PA is introduced. In its current version, GeTeX supports Control Area Network (CAN) applications. GeTeX is validated by developing a prototype for that purpose. Using GeTeX, PA is also empirically validated in comparison with some TA testing approaches using a complete industrial-strength test bed. The assessment is based on fault coverage, structural coverage, the length of generated test cases and a proposed assessment factor. The assessment is based on fault coverage, structural coverage, the length of generated test cases and a proposed assessment factor. The assessment results confirmed the superiority of PA over the other test approaches. The overall assessment factor showed that structural and fault coverage scores of PA with respect to the length of its tests were better than the others proving the applicability of PA. Finally, an Analytical Hierarchy Process (AHP) decision-making framework for our PA is developed. The framework can provide testers with a systematic approach by which they can prioritise the available PA test sets that best fulfils their testing requirements. The AHP framework developed is based on the data collected heuristically from the test bed and data collected by interviewing testing experts. The framework is then validated using two testing scenarios. The decision outcomes of the AHP framework were significantly correlated to those of testing experts which demonstrated the soundness and validity of the framework.
23
Ericsson, Ann-Marie. "Verifying transformations between timed automata specifications and ECA rules." Thesis, University of Skövde, Department of Computer Science, 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:his:diva-823.
Full textAbstract:
Event-triggered real-time systems are desirable to use in environments where the arrival of events are hard to predict. The semantics of an event-triggered system is well mapped to the behaviour of an active database management system (ADBMS), specified using event-condition-action (ECA) rules. The benefits of using an active database, such as persistent data storage, concurrency control, timely response to event occurrences etc. highlights the need for a development method for event-triggered real-time systems using active databases.
However, there are problems left to be solved before an ADBMS can be used with confidence in real-time environments. The behaviour of a real-time system must be predictable, which implies a thorough analysed specification with e.g. specified worst case execution times. The predictability requirement is an obstacle for specifying real-time systems as ECA rules, since the rules may affect each other in many intricate ways which makes them hard to analyse. The interaction between the rules implies that it is not enough to verify the correctness of single rules; an analysis must consider the behaviour of the entire rule set.
In this dissertation, an approach for developing active applications is presented. A method is examined which starts with an analysed high-level timed automaton specification and transforms the specified behaviour into an implicitly analysed rule set. For this method to be useful, the transformation from timed automata to rules must preserve the exact behaviour of the high level specification. Hence, the aim of this dissertation is to verify transformations between timed automaton specifications and ECA rules.
The contribution of this project is a structured set of general transformations between timed automata specifications and ECA rules. The transformations include both transformations of small timed automata constructs for deterministic environments and formally verified timed automata patterns specifying the behaviour of composite events in recent and chronicle context.
24
Ausmees, Kristiina. "Zone-Based Reachability Analysis of Dense-Timed Pushdown Automata." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-179802.
Full textAbstract:
Proving that programs behave correctly is a matter of both great theoretical interest as well as practical use. One way to do this is by analyzing a model of the system in question in order to determine if it meets a given specification. Real-time recursive systems can be modeled by dense-timed pushdown automata, a model which combines the behaviours of classical timed automata and pushdown automata. The problem of reachability has been proven to be decidable for this model. The algorithm that solves this problem relies on constructing a classical pushdown automaton that mimics the behaviour of a given timed pushdown automaton by means of an abstraction that uses regions as a symbolic representation of states. The drawback of this approach is that the untimed automaton produced generally contains a very large number of states. This report proposes a method of generalizing this abstraction by using zones instead of regions, in order to minimize the number of states in the untimed automaton.
25
Herrera, Christian [Verfasser], and Andreas [Akademischer Betreuer] Podelski. "The class of timed automata with quasi-equal clocks." Freiburg : Universität, 2017. http://d-nb.info/1152944584/34.
Full text
26
Bourke, Timothy Peter Computer Science & Engineering Faculty of Engineering UNSW. "Modelling and programming embedded controllers with timed automata and synchronous languages." Awarded by:University of New South Wales. Computer Science & Engineering, 2009. http://handle.unsw.edu.au/1959.4/44746.
Full textAbstract:
Embedded controllers coordinate the behaviours of specialised hardware components to satisfy broader application requirements. They are difficult to model and to program. One of the greatest challenges is to express intricate timing behaviours???which arise from the physical characteristics of components???while not precluding efficient implementations on resource-constrained platforms. Aspects of this challenge are addressed by this thesis through four distinct applications of timed automata and the synchronous languages Argos and Esterel. A novel framework for simulating controllers written in an imperative synchronous language is described. It includes a transformation of synchronous models into timed automata that accounts for timing properties which are important in constrained implementations but ignored by the usual assumption of synchrony. The transformation provides an interface between the discrete time of synchronous programs and a continuous model of time. This interface is extended to provide a way for simulating Argos programs within the widely-used Simulink software. Timed automata are well-suited for semantic descriptions, like the aforementioned transformation, and for modelling abstract algorithms and protocols. This thesis also includes a different type of case study. The timing diagram of a small-scale embedded component is modelled in more detail than usual with the aim of studying timing properties in this type of system. Multiple models are constructed, including one of an assembly language controller. Their interrelations are verified in Uppaal using a construction for timed trace inclusion testing. Existing constructions for testing timed trace inclusion do not directly address recent features of the Uppaal modelling language. Novel solutions for the problems presented by selection bindings, quantifiers, and channel arrays in Uppaal are presented in this thesis. The first known implementation of a tool for automatically generating a timed trace inclusion construction is described. The timed automata case study demonstrates one way of implementing application timing behaviours while respecting implementation constraints. A more challenging, but less detailed, example is proposed to evaluate the adequacy of Esterel for such tasks. Since none of the standard techniques are completely adequate, a novel alternative for expressing delays in physical time is proposed. Programs in standard Esterel are recovered through syntactic transformations that account for platform constraints.
27
Doyen, Laurent. "Algorithmic analysis of complex semantics for timed and hybrid automata." Doctoral thesis, Universite Libre de Bruxelles, 2006. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210853.
Full textAbstract:
In the field of formal verification of real-time systems, major developments have been recorded in the last fifteen years. It is about logics, automata, process algebra, programming languages, etc. From the beginning, a formalism has played an important role: timed automata and their natural extension,hybrid automata. Those models allow the definition of real-time constraints using real-valued clocks, or more generally analog variables whose evolution is governed by differential equations. They generalize finite automata in that their semantics defines timed words where each symbol is associated with an occurrence timestamp.The decidability and algorithmic analysis of timed and hybrid automata have been intensively studied in the literature. The central result for timed automata is that they are positively decidable. This is not the case for hybrid automata, but semi-algorithmic methods are known when the dynamics is relatively simple, namely a linear relation between the derivatives of the variables.
With the increasing complexity of nowadays systems, those models are however limited in their classical semantics, for modelling realistic implementations or dynamical systems.
In this thesis, we study the algorithmics of complex semantics for timed and hybrid automata.
On the one hand, we propose implementable semantics for timed automata and we study their computational properties: by contrast with other works, we identify a semantics that is implementable and that has decidable properties.
On the other hand, we give new algorithmic approaches to the analysis of hybrid automata whose dynamics is given by an affine function of its variables.
Doctorat en sciences, Spécialisation Informatique
info:eu-repo/semantics/nonPublished
28
Sproston, Jeremy James. "Model checking of probabilistic timed and hybrid systems." Thesis, University of Birmingham, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.391021.
Full text
29
Larsson, Fredrik. "Efficient implementation of model-checkers for networks of timed automata." Licentiate thesis, Uppsala universitet, Avdelningen för datorteknik, 2000. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-226511.
Full textAbstract:
Since real-time systems often operate in safety-critical environments it is extremely important that they function correctly. UPPAAL is a tool that can be used for validation and verification of real-time systems. The user models the system using networks of timed automata and uses a simple logic to express safety requirements that the modelled system must satisfy to guarantee its correct behaviour. UPPAAL then performs reachability analysis using constraint solving techniques to check if the model satisfies the given requirements. In addition, the tool is also able to provide the user with a sample execution that explains why a requirement is (or is not) satisfied by the model. The analysis is fully automated. This thesis describes various techniques adopted when implementing UPPAAL. Some of the techniques have improved the performance of UPPAAL significantly. We have studied the techniques with performance measurements in several case-studies. One of the main contributions is the comparison of different strategies in implementing the basic data structures and searching algorithms. The measurements can be used as hints on what parts of the model-checker that are most important to optimise. Though the techniques are studied in the context of timed automata, we believe that they are applicable to the implementation of general software tools for automated analysis.
30
Troina, Angelo [Verfasser]. "Probabilistic Timed Automata for Security Analysis and Design / Angelo Troina." Munich : GRIN Publishing, 2017. http://d-nb.info/1138030554/34.
Full text
31
Ramparison, Mathias. "On the theory and practice of updatable parametric timed automata." Thesis, Paris 13, 2019. http://www.theses.fr/2019PA131063.
Full textAbstract:
A mesure que les systèmes cyber-physiques deviennent de plus en plus complexes,le débogage humain ne suffit plus pour analyser le grand nombre de comportements possibles. Pour les systèmes critiques coûteux où des vies humaines peuvent être mise sen danger, il est encore plus crucial de prouver formellement la sécurité d'un système.Pour ce faire, on définit une spécification formelle pour le système, puis on vérifie algorithmiquement que le système satisfait à certaines propriétés spécifiées de manière formelle. Avec cette description précise et exhaustive d'un système, le ou habituel du langage humain est éliminé. Dans cette thèse, nous nous concentrons sur la vérification des systèmes concurrents temporisés. Les systèmes dépendant du temps sont très difficiles à vérifier, en particulier lorsque la valeur exacte des constantes de synchronisation reste inconnue. Ces constantes de synchronisation inconnues sont appelées paramètres.Nous étudions plusieurs sous-classes d'une extension paramétrique d'un formalisme bien connu, les automates temporisés. Nous nous concentrons principalement sur le problème de décision de l'accessibilité, qui pose la question de l'existence de valeurs concrètes pour ces paramètres telles qu'un état de bogue peut être atteint dans le système. Nous abordons en outre pour ces sous-classes un problème de calcul consistant à synthétiser l'ensemble des valeurs de paramètres pour lesquelles un état est accessible.Enfin, nous appliquons nos travaux à la sécurité des infrastructures et des systèmes cyber-physiques : nous étendons avec des paramètres un formalisme classique pour modéliser des scénarios d'attaque et de défaillance, appelés arbres de défaillance et d'attaque, et proposons une implémentation de la traduction d'arbres de défaillance et d'attaque paramétriques en automates paramétrés temporisés. Cela nous permet de tirer parti des techniques et des outils de vérification disponibles pour ce formalisme pour l'analyse des arbres de défaillance et d'attaque (paramétriques)As cyber-physical systems become more and more complex, human debugging is not sufficient anymore to cover the huge range of possible behaviours. For costly critical systems where human lives can be endangered, formally proving the safety of a systemis even more crucial. This is done by defining a formal specification for the system, and then performing the algorithmic verification that the system satisfies some formally specified properties. With this precise and exhaustive description of a system, the usual vagueness of human language is eliminated. In this thesis, we focus on the verification of timed concurrent systems. Time-dependent systems are very hard toverify, especially when the exact value of timing constants remains unknown. Theseunknown timing constants are called parameters. We study several subclasses of aparametric extension of the well-known formalism called Timed Automata. We mainly focus on the reachability decision problem, that asks whether there exists concrete values for these parameters such that a bug state can be reached in the system. We further address for these subclasses a computation problem that is to synthesise the set of parameter values for which a state is reachable. Finally, we apply our work to the security and safety of cyber-physical systems and infrastructure : we extend with parameters a classic formalism to model attack and failure scenarios called attack-fault trees, and propose an implementation of the translation of parametric attack-fault trees to parametric timed automata. This allows us to leverage the verification techniques and tools available for the latter for the analysis of (parametric) attack-fault trees
32
M'Hemdi, Hana. "Contributions à la génération de tests à partir d'automates à pile temporisés." Thesis, Besançon, 2016. http://www.theses.fr/2016BESA2050/document.
Full textAbstract:
La vérification et la validation des composants logiciels des systèmes temps réel est un des enjeuxmajeurs pour le développement de systèmes automatisés. Les modèles de tels systèmes doiventêtre vérifiés, et la conformité de leur implémentation par rapport à leur modèle doit être validée. Nous nous plaçons dans le cadre des systèmes récursifs temps réels modélisables par des automates à pile temporisés avec deadlines (TPAIO). Les deadlines imposent des conditions de progression du temps. L’objectif de cette thèse est de proposer des méthodes de génération de tests pour les TPAIO.Nos contributions sont les suivantes. Premièrement, une relation de conformité pour les TPAIO est introduite. Deuxièmement, une méthode polynomiale de génération de tests à partir d’un TPAIO déterministe avec deadline lazy est définie. Elle consiste à définir un algorithme de calcul d’un automate temporisé d’accessibilité incomplet en respectant les contraintes de pile. Cette méthode est incomplète. L’incomplétude n'étant pas un problème car l’activité de test est par essence incomplète. Troisièmement, nous définissons une méthode générant des cas de tests à partir d’un TPAIO déterministe avec sorties seulement et deadline delayable seulement. Elle d’applique aux abstractions de programmes récursifs temporisés. Elle consiste à générer des cas de tests en calculant un testeur sur-approximé. Finalement, nous avons proposé une généralisation du processus de génération de tests à partir d’un TPAIO général avec entrées/sorties et avec deadlines quelconques. La capacité de cette dernière méthode à détecter des implémentations non conformes est évaluée par une technique de mutationThe verification and validation of software components for real-time systems is a major challenge for the development of automated systems. The models of such systems must be verified and the conformance of their implementation w.r.t their model must be validated. Our framework is that of real-time recursive systems modelled by timed pushdown automata with deadlines (TPAIO). The deadlines impose time progress conditions. The objective of this thesis is to propose test generation methods from TPAIO.Our contributions are as follows. Firstly, a conformance relation for TPAIO is introduced. Secondly, a polynomial method of test generation from a deterministic TPAIO with only lazy deadlines is defined. It consists of defining a polynomial algorithm that computes a partial reachability timed automaton by removing the stack constraints. This method is incomplete. The incompleteness is not a problem because software testing is an incomplete activity by nature. Thirdly, we define a method for generating test cases from a deterministic TPAIO with only outputs and delayable deadlines. It applies to the abstractions of timed recursive programs. It consists of generating test cases by computing an over-approximated tester. Finally, we propose a generalization of the test generation process from a non deterministic TPAIO with any deadlines. Its ability to detect non conform implementation is assessed by a mutation technique
33
Gani, Kahina. "Using timed automata formalism for modeling and analyzing home care plans." Thesis, Clermont-Ferrand 2, 2015. http://www.theses.fr/2015CLF22628/document.
Full textAbstract:
Dans cette thèse nous nous sommes intéressés aux problèmes concernant la conception et la gestion des plans de soins à domicile. Un plan de soins à domicile définit l'ensemble des activités médicales et/ou sociales qui sont menées jour après jour au domicile d'un patient. Ce plan de soins est généralement construit à travers un processus complexe impliquant une évaluation complète des besoins du patient ainsi que son environnement social et physique. La spécification de plans de soins à domicile est difficile pour plusieurs raisons: les plans de soins à domicile sont par nature des processus non structurés qui impliquent des activités répétitives mais irrégulières, dont la spécification requiert des expressions temporelles complexes. Ces caractéristiques font que les plans de soins à domicile sont difficiles à modéliser en utilisant les technologies traditionnelles de modélisation de processus. Tout d'abord, nous présentons l'approche basée sur les DSL (Langage spécifique au domaine) qui permet d'exprimer les plans de soins à domicile en utilisant des abstractions de haut niveau et orientées utilisateur. Le DSL nous permet à travers cette thèse de proposer un langage de temporalités permettant de spécifier les temporalités des activités du plan de soins à domicile. Ensuite, nous décrivons comment les plans de soins à domicile, formalisés grâce aux automates temporisés, peuvent être générés à partir de ces abstractions. Nous proposons une approche en trois étapes qui consiste à: (i) le mapping entre les spécifications temporelles élémentaires et les automates temporisés appelés "pattern automata", (ii) la combinaison des "patterns automata" afin de construire les automates d'activités en utilisant l'algorithme de composition que nous avons déni, et aussi (iii) la construction de l'automate de plan de soins à domicile global. L'automate de plan de soins à domicile résultant englobe tous les schedules autorisés des activités pour un patient donné. Enfin, nous montrons comment la vérification et le suivi de l'automate du plan de soins à domicile résultant peuvent être faits en utilisant des techniques et des outils existants, en particulier en utilisant l'outil de verification UPPAALIn this thesis we are interested in the problems underlying the design and the management of home care plans. A home care plan defines the set of medical and/or social activities that are carried out day after day at a patient's home. Such a care plan is usually constructed through a complex process involving a comprehensive assessment of patient's needs as well as his/her social and physical environment. Specication of home care plans is challenging for several reasons: home care plans are inherently nonstructured processes which involve repetitive, but irregular, activities, whose specification requires complex temporal expressions. These features make home care plans difficult to model using traditional process modeling technologies. First, we present a DSL (Domain Specific Language) based approach tailored to express home care plans using high level and user-oriented abstractions. DSL enables us through this thesis to propose a temporalities language to specify temporalities of home care plan activities. Then, we describe how home care plans, formalized as timed automata, can be generated from these abstractions. We propose a three-step approach which consists in (i) mapping between elementary temporal specifications and timed automata called Pattern automata, (ii) combining patterns automata to build the activity automata using our composition algorithm and then (iii) constructing the global care plan automaton. The resulting care plan automaton encompasses all the possible allowed schedules of activities for a given patient. Finally, we show how verification and monitoring of the resulting care plan can be handled using existing techniques and tools, especially using UPPAAL Model Checker
34
Basset, Nicolas. "Volumetry of timed languages and applications." Thesis, Paris Est, 2013. http://www.theses.fr/2013PEST1073/document.
Full textAbstract:
Depuis le début des années 90, les automates temporisés et les langages temporisés ont été largement utilisés pour modéliser et vérifier les systèmes temps réels. Ces langages ont été aussi été largement étudiés d'un point de vue théorique. Plus récemment Asarin et Degorre ont introduit les notions de volume et d'entropie des langages temporisés pour quantifier la taille de ces langages et l'information que ses éléments contiennent. Dans cette thèse nous construisons de nouveaux développements à cette théorie (que nous appelons volumétrie des langages temporisés) et l'appliquons a plusieurs problèmes apparaissant dans divers domaine de recherche tel que la théorie de l'information, la vérification, la combinatoire énumérative. Entre autre nous (i) développons une théorie de la dynamique symbolique temporisée~; (ii) caractérisons une dichotomie entre automate temporisé se comportant bien ou mal~; (iii) définissons pour un automate temporisé donné, un processus stochastique d'entropie maximale le moins biaisé possible~; (iv) développons une version temporisé de la théorie des codes sur canal contraint (v) énumérons et générons aléatoirement des permutations dans une certaine classeSince early 90s, timed automata and timed languages are extensively used for modelling and verification of real-time systems, and thoroughly explored from a theoretical standpoint. Recently Asarin and Degorre introduced the notions of volume and entropy of timed languages to quantify the size of these languages and the information content of their elements. In this thesis we build new developments of this theory (called by us volumetry of timed languages) and apply it to several problems occurring in various domains of theoretical computer science such as verification, enumerative combinatorics or information theory. Among other we (i) develop a theory of timed symbolic dynamics; (ii) characterize a dichotomy between bad behaving and well behaving timed automata; (iii) define a least biased stochastic process for a timed automaton; (iv) develop a timed theory of constrained channel coding; (v)count and generate randomly and uniformly permutations in certain classes
35
Busatto-Gaston, Damien. "Symbolic controller synthesis for timed systems : robustness and optimality." Electronic Thesis or Diss., Aix-Marseille, 2019. http://www.theses.fr/2019AIXM0461.
Full textAbstract:
Le domaine de la synthèse réactive a pour objectif d'obtenir un système correct par construction à partir d'une spécification logique.Une approche classique consiste à se ramener à un jeu à somme nulle,où deux joueurs interagissent tour-à-tour dans un système de transitions, et à se demander si le joueur "contrôleur" peut garantir que son objectif sera rempli, et ce indépendamment des décisions du joueur "environnement".Nous étudions des spécifications temps-réel, modélisées par un automate temporisé équipé d'un objectif d'accessibilité ou de Büchi, et présentons des méthodes symboliques pour synthétiser des stratégies du contrôleur.Nos contributions concernent deux problématiques distinctes :on peut souhaiter que le contrôleur obtienne une stratégie robuste aux perturbations,ou bien le faire jouer de manière optimale dans un jeu pondéréThe field of reactive synthesis studies ways to obtain,starting from a specification, a system that is correctby construction.A classical approach models this setting as azero-sum game played by two players on a transition system,and asks whether player controller canensure an objective against any competing player environment.We focus on real-time specifications,modelled as timed automata with reachability or Büchi acceptance conditions,and present symbolic ways to synthesise strategies for the controller.We consider two problems, either restricting controller to robust strategiesor aiming for optimal strategies in a weighted game setting
36
Ciatto, Giovanni. "Third generation neural networks: formalization as timed automata, validation and learning." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2017. http://amslaurea.unibo.it/12947/.
Full textAbstract:
Questa tesi mostra una formalizzazione delle reti neurali spiking ottenuta tramite automi temporizzati. Tali reti, a differenza di quelle di seconda generazione, tengono conto anche della dimensione temporale. Sono mostrate due codifiche, sincrona e asincrona, del modello "leaky integrate and fire": i neuroni sono modellati come automi temporizzati che attendono impulsi su dei canali di ingresso e aggiornano il potenziale in base agli input presenti e passati, modulati dai pesi delle rispettive sinapsi e tanto più influenti quanto più recenti. Se il potenziale supera una certa soglia, l'automa emette un segnale sul canale di uscita. Dopo ogni emissione i neuroni rimangono silenti per un periodo refrattario fissato per poi resettarsi. Nel modello asincrono gli input si assumono molto frequenti ma non possono essere contemporanei. In quello sincrono tutti gli impulsi ricevuti nello stesso periodo di accumulazione sono simultanei. Una rete neurale è ottenuta eseguendo in parallelo più automi che condividono canali opportunamente. Anche le sequenze in input sono specificate tramite automi temporizzati, detti generatori, ottenuti tramite un procedimento automatico, da un linguaggio che modella sequenze di spike e pause. Per il modello sincrono si verifica la capacità di riprodurre alcuni comportamenti noti in letteratura. Esso è poi sfruttato per trovare i pesi sinaptici che permettano ad una rete di riprodurre un comportamento dato, espresso tramite logica temporale. Ciò è ottenuto tramite un algoritmo che identifica gli errori commessi dai neuroni di output e applica delle azioni correttive sulle loro sinapsi in ingresso. Le informazioni sulle azioni correttive adeguate vengono poi propagate all'indietro verso gli altri neuroni della rete. Questo processo è ripetuto fino alla riproduzione del comportamento desiderato. Due gli approcci implementativi presentati: uno basato sulla simulazione e uno basato sul model-checking.
37
Lim, Hongping. "Translating timed I/O automata specifications for theorem proving in PVs." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/36803.
Full textAbstract:
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.Includes bibliographical references (leaves 68-70).
The timed input/output automaton modeling framework is a mathematical framework for specification and analysis of systems that involve discrete and continuous evolution. In order to employ an interactive theorem prover in deducing properties of a timed input/output automaton, its state-transition based description has to be translated to the language of the theorem prover. This thesis describes a tool for translating from TIOA, the formal language for describing timed input/output automata, to the language of the Prototype Verification System (PVS)--a specification system with an integrated interactive theorem prover. We describe the translation scheme, discuss the design decisions, and briefly present case studies to illustrate the application of the translator in the verification process.
by Hongping Lim.
M.Eng.
38
Krause, Christian, and Holger Giese. "Quantitative modeling and analysis of service-oriented real-time systems using interval probabilistic timed automata." Universität Potsdam, 2012. http://opus.kobv.de/ubp/volltexte/2012/5784/.
Full textAbstract:
One of the key challenges in service-oriented systems engineering is the prediction and assurance of non-functional properties, such as the reliability and the availability of composite interorganizational services. Such systems are often characterized by a variety of inherent uncertainties, which must be addressed in the modeling and the analysis approach. The different relevant types of uncertainties can be categorized into (1) epistemic uncertainties due to incomplete knowledge and (2) randomization as explicitly used in protocols or as a result of physical processes.
In this report, we study a probabilistic timed model which allows us to quantitatively reason about nonfunctional properties for a restricted class of service-oriented real-time systems using formal methods. To properly motivate the choice for the used approach, we devise a requirements catalogue for the modeling and the analysis of probabilistic real-time systems with uncertainties and provide evidence that the uncertainties of type (1) and (2) in the targeted systems have a major impact on the used models and require distinguished analysis approaches.
The formal model we use in this report are Interval Probabilistic Timed Automata (IPTA). Based on
the outlined requirements, we give evidence that this model provides both enough expressiveness for a realistic and modular specifiation of the targeted class of systems, and suitable formal methods for analyzing properties, such as safety and reliability properties in a quantitative manner. As technical means for the quantitative analysis, we build on probabilistic model checking, specifically on probabilistic time-bounded reachability analysis and computation of expected reachability rewards and costs. To carry out the quantitative analysis using probabilistic model checking, we developed an extension of the Prism tool for modeling and analyzing IPTA. Our extension of Prism introduces a means for modeling probabilistic uncertainty in the form of probability intervals, as required for IPTA. For analyzing IPTA, our Prism extension moreover adds support for probabilistic reachability checking and computation of expected rewards and costs. We discuss the performance of our extended version of Prism and compare the interval-based IPTA approach to models with fixed probabilities.Eine der wichtigsten Herausforderungen in der Entwicklung von Service-orientierten Systemen ist die Vorhersage und die Zusicherung von nicht-funktionalen Eigenschaften, wie Ausfallsicherheit und Verfügbarkeit von zusammengesetzten, interorganisationellen Diensten. Diese Systeme sind oft charakterisiert durch eine Vielzahl von inhärenten Unsicherheiten, welche sowohl in der Modellierung als auch in der Analyse eine Rolle spielen. Die verschiedenen relevanten Arten von Unsicherheiten können eingeteilt werden in (1) epistemische Unsicherheiten aufgrund von unvollständigem Wissen und (2) Zufall als Mittel in Protokollen oder als Resultat von physikalischen Prozessen. In diesem Bericht wird ein probabilistisches, Zeit-behaftetes Modell untersucht, welches es ermöglicht quantitative Aussagen über nicht-funktionale Eigenschaften von einer eingeschränkten Klasse von Service-orientierten Echtzeitsystemen mittels formaler Methoden zu treffen. Zur Motivation und Einordnung wird ein Anforderungskatalog für probabilistische Echtzeitsysteme mit Unsicherheiten erstellt und gezeigt, dass die Unsicherheiten vom Typ (1) und (2) in den untersuchten Systemen einen Ein uss auf die Wahl der Modellierungs- und der Analysemethode haben. Als formales Modell werden Interval Probabilistic Timed Automata (IPTA) benutzt. Basierend auf den erarbeiteten Anforderungen wird gezeigt, dass dieses Modell sowohl ausreichende Ausdrucksstärke für eine realistische und modulare Spezifikation als auch geeignete formale Methoden zur Bestimmung von quantitativen Sicherheits- und Zuverlässlichkeitseigenschaften bietet. Als technisches Mittel für die quantitative Analyse wird probabilistisches Model Checking, speziell probabilistische Zeit-beschränkte Erreichbarkeitsanalyse und Bestimmung von Erwartungswerten für Kosten und Vergütungen eingesetzt. Um die quantitative Analyse mittels probabilistischem Model Checking durchzuführen, wird eine Erweiterung des Prism-Werkzeugs zur Modellierung und Analyse von IPTA eingeführt. Die präsentierte Erweiterung von Prism ermöglicht die Modellierung von probabilistischen Unsicherheiten mittelsWahrscheinlichkeitsintervallen, wie sie für IPTA benötigt werden. Zur Verifikation wird probabilistische Erreichbarkeitsanalyse und die Berechnung von Erwartungswerten durch das Werkzeug unterstützt. Es wird die Performanz der Prism-Erweiterung untersucht und der Intervall-basierte IPTA-Ansatz mit Modellen mit festen Wahrscheinlichkeitswerten verglichen.
39
Muhajab, Hanan Nasser. "EXTENDED COUPLED PROBABLISTIC TIMED AUTOMATA FOR MONITORING EATING ACTIVITIES OF ELDERLY PERSON." Kent State University / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=kent1479812233555067.
Full text
40
Perevoshchikov, Vitaly. "Multi-weighted Automata Models and Quantitative Logics." Doctoral thesis, Universitätsbibliothek Leipzig, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-166142.
Full textAbstract:
Recently, multi-priced timed automata have received much attention for real-time systems. These automata extend priced timed automata by featuring several price parameters. This permits to compute objectives like the optimal ratio between rewards and costs. Arising from the model of timed automata, the multi-weighted setting has also attracted much notice for classical nondeterministic automata.
The present thesis develops multi-weighted MSO-logics on finite, infinite and timed words which are expressively equivalent to multi-weighted automata, and studies decision problems for them. In addition, a Nivat-like theorem for weighted timed automata is proved; this theorem establishes a connection between quantitative and qualitative behaviors of timed automata. Moreover, a logical characterization of timed pushdown automata is given.
41
Hatvani, Leo. "Formal Verification of Adaptive Real-Time Systems by Extending Task Automata." Licentiate thesis, Mälardalens högskola, Inbyggda system, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-26129.
Full textAbstract:
Recently, we have seen an increase in the deployment of safety critical embedded systems in rapidly changing environments, as well as requirement for on-site customizations and rapid adaptation. To address the extended range of requirements, adaptation mechanism are added to the systems to handle large number of situations appropriately. Although necessary, adaptations can cause inconsistent and unstable configurations that must be prevented for the embedded system to remain dependable and safe. Therefore, verifying the behavior of adaptive embedded systems during the design phase of the production process is highly desirable. A hard real time embedded system and its environment can be modeled using timed automata. Such model can describe the system at various levels of abstraction. In this thesis, we model the adaptive responses of a system in terms of tasks that are executed to handle changes in the environmental or internal parameters. Schedulability, a property that all tasks complete execution within their respective deadlines, is a key element in designing hard real-time embedded systems. A system that is unschedulable immediately compromises safety and hard real-time requirements and can cause fatal failure. Given specifications of all tasks in the system, we can model the system, an abstraction of the environment, and adaptive strategies to investigate whether the system retains safety properties, including schedulability, regardless of the changes in the environment and adaptations to those changes.
42
Rinast, Jonas [Verfasser], and Sibylle [Akademischer Betreuer] Schupp. "An online model-checking framework for timed automata / Jonas Rinast. Betreuer: Sibylle Schupp." Hamburg : Universitätsbibliothek der Technischen Universität Hamburg-Harburg, 2015. http://d-nb.info/1077042043/34.
Full text
43
Suryadevara, Jagadish. "Model Based Development of Embedded Systems using Logical Clock Constraints and Timed Automata." Doctoral thesis, Mälardalens högskola, Akademin för innovation, design och teknik, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-22328.
Full textAbstract:
In modern times, human life is intrinsically depending on real-time embedded systems (RTES) with increasingly safety-critical and mission-critical features, for instance, in domains such as automotive and avionics. These systems are characterized by stringent functional requirements and require predictable timing behavior. However, the complexity of RTES has been ever increasing requiring systematic development methods. To address these concerns, model-based frameworks and component-based design methodologies have emerged as a feasible solution. Further, system artifacts such as requirements/specifications, architectural designs as well as behavioral models like statemachine views are integrated within the development process. However, several challenges remain to be addressed, out of which two are especially important: expressiveness, to represent the real-time and causality behavior, and analyzability, to support verification of functional and timing behavior. As the main research contribution, this thesis presents design and verification techniques for model-based development of RTES, addressing expressiveness and analyzability for architectural and behavioral models. To begin with, we have proposed a systematic design process to support component-based development. Next, we have provided a real-time semantic basis, in order to support expressiveness and verification for structural and behavioral models. This is achieved by defining an intuitive formal semantics for real-time component models, using ProCom, a component model developed at our research centre, and also using the CCSL (Clock Constraint Specification Language), an expressive language for specification of timed causality behavior. This paves the way for formal verification of both architectural and behavioral models, using model checking, as we show in this work, by transforming the models into timed automata and performing verification using UPPAAL, a model checking tool based on timed automata. Finally, the research contributions are validated using representative examples of RTES as well as an industrial case-study.ARROWS
44
Rinast, Jonas Verfasser], and Sibylle [Akademischer Betreuer] [Schupp. "An online model-checking framework for timed automata / Jonas Rinast. Betreuer: Sibylle Schupp." Hamburg : Universitätsbibliothek der Technischen Universität Hamburg-Harburg, 2015. http://nbn-resolving.de/urn:nbn:de:gbv:830-88213142.
Full text
45
Jaziri, Samy. "Automate sur les structures temporisée." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLN039/document.
Full textAbstract:
Les systèmes digitaux jouent un rôle croissant dans le bon fonctionnement de notre société.Au delà de la grande diversité de leur domaines d'utilisations, on confie aujourd'hui destâches importantes à des algorithmes. Déjà largement utilisés dans des domaines aussi délicatque le transport, la chirurgie ou l'économie, il est aujourd'hui de plus en plus question defaire de la place aux systèmes digitaux dans les domaines sociaux et politiques :vote électronique, algorithmes de sélection, profilage électoraldotsPour les tâches confiées à des algorithmes, la responsabilité est déplacées de l'exécutantvers les concepteurs, développeurs et testeurs de ces algorithmes. Il incombe aussi auxchercheurs qui étudient ces algorithmes de proposer des techniques de vérifications fiablequi pourront être utilisées à tous les niveaux : conception, développement et test.Les méthodes de vérifications formelles donnent des outils mathématiques pourprévenir des erreurs à chaque niveaux. Parmi elle, le diagnostic d'erreur consiste en lacréation d'un diagnostiqueur basé sur un modèle formel du système à vérifier.Le diagnostiqueur est exécuté en parallèle du système qu'il doit surveiller et prévientun contrôleur si il détecte un comportement dangereux du système.Pour les systèmes modélisés par des automates temporisés, il n'est pas toujours possiblede construire un diagnostiqueur sous la forme d'un autre automate temporisé. En effetles automates temporisés, introduits par cite{AD94} dans les années 90 et largementétudiés et utilisés depuis pour modéliser des systèmes avec contraintes temporelles,ne sont pas déterminisable. Une machine plus puissante qu'un automate temporisé peutcependant être utilisée pour construire le diagnostiqueur d'un automate temporisé commele montre cite{Tripakis02}. L'aboutissement de ce travail de thèse est la constructionautomatique d'un diagnostiqueur pour les automates temporisés à une horloge.Ce diagnostiqueur, dans le même esprit que celui de cite{Tripakis02}, est une machineplus puissante qu'un automate temporisé. La partie~I du manuscrit introduit un cadreformel pour ce type de machine et plus généralement pour la modélisation et ladéterminisation de systèmes quantitatifs. Y est introduit le modèle des automates surstructures temporisés, qui apporte un nouveau point de vue sur la manière de modéliserles systèmes avec variables quantitatives. La partie~II étudie le problème de ladéterminisation des automates sur structures temporises, et plus spécifiquement celuides automates temporisés qui peuvent se traduire dans ce cadre nouveau cadre formel.La partie~III montre comment utiliser les automates sur structure temporisés pourconstruire de manière générique un diagnostiqueur pour les automate temporisés à unehorloge. Cette technique est implémentée dans un outils, DOTA , et comparée à lamachine construite par cite{Tripakis02}Digital system are now part of our society. They are used in a wide range of domainsand in particular they have to handle delicate tasks. Already used in domainssuch as transportation, surgery or economy, we speak now of using digital systemsfor social or political matters : electronic vote, selection algorithms, electoralprofilingdots For task handled by algorithm, the responsibility is moved from theexecutioner to the designer, developer and tester of those algorithms. It is alsothe responsibility of computer scientists who study those algorithms to proposereliable techniques of verification which will be applicable in the design, thedevelopment or the testing phase. Formal verification methods provide mathematicaltools to prevent executions error in all phases. Among them, fault-diagnosis consiston the construction of a diagnoser based on a formal model of the system we aim tocheck. The diagnoser runs in parallel with the real system and emit a warning anytime it detect a dangerous behavior. For systems modeled by timed automata, it isnot always possible to construct a timed automaton to diagnose it. Indeed timed automata,introduce in the nineties by cite{AD94} and widely studied and used since to modeltimed systems, are not determinizable. A machine, more powerful than a timed automaton,can still be used to construct the diagnoser of a timed automaton as it is done incite{Tripakis02}. This thesis work aim at constructing a diagnoser for any one-clocktimed automata. This diagnoser is constructed with the help of a machine more powerfulthan timed automata, following the idea of cite{Tripakis02}. Part~I of this thesisintroduce a formal framework for the modeling of quantitative systems and the study oftheir determinization. In this framework we introduce automata on timed structures,the model used to construct the diagnoser. Part~II study the determinization problemof automata on timed structures, and particularly the one of timed automatadeterminization in this framework. Part~III illustrate how automata on timed structurescan be used to construct in a generic way a diagnoser for one clock timed automata.This technique is implemented in a tool, DOTA , and is compared to the technique usedin cite{Tripakis02}
46
Jenkins, Mark Daniel. "Synthesis and alternating automata over real time." Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:f37ccc5f-8ed6-4b00-b9e3-28c4bb4ec60a.
Full textAbstract:
Alternating timed automata are a powerful extension of classical Alur-Dill timed automata that are closed under all Boolean operations. They have played a key role, among others, in providing verification algorithms for prominent specification formalisms such as Metric Temporal Logic. Unfortunately, when interpreted over an infinite dense time domain (such as the reals), alternating timed automata have an undecidable language emptiness problem. In this thesis we consider restrictions on this model that restore the decidability of the language emptiness problem. We consider the restricted class of safety alternating timed automata, which can encode a corresponding Safety fragment of Metric Temporal Logic. This thesis connects these two formalisms with insertion channel machines, a model of faulty communication, and demonstrates that the three formalisms are interreducible. We thus prove a non-elementary lower bound for the language emptiness problem for 1-clock safety alternating timed automata and further obtain a new proof of decidability for this problem. Complementing the restriction to safety properties, we consider interpreting the automata over bounded dense time domains. We prove that the time-bounded language emptiness problem is decidable but non-elementary for unrestricted alternating timed automata. The language emptiness problem for alternating timed automata is a special case of a much more general and abstract logical problem: Church's synthesis problem. Given a logical specification S(I,O), Church's problem is to determine whether there exists an operator F that implements the specification in the sense that S(I,F(I)) holds for all inputs I. It is a classical result that the synthesis problem is decidable in the case that the specification and implementation are given in monadic second-order logic over the naturals. We prove that this decidability extends to MSO over the reals with order and furthermore to MSO over every fixed bounded interval of the reals with order and the +1 relation.
47
Bundala, Daniel. "Algorithmic verification problems in automata-theoretic settings." Thesis, University of Oxford, 2014. https://ora.ox.ac.uk/objects/uuid:60b2d507-153f-4119-a888-56ccd47c3752.
Full textAbstract:
Problems in formal verification are often stated in terms of finite automata and extensions thereof. In this thesis we investigate several such algorithmic problems. In the first part of the thesis we develop a theory of completeness thresholds in Bounded Model Checking. A completeness threshold for a given model M and a specification φ is a bound k such that, if no counterexample to φ of length k or less can be found in M, then M in fact satisfies φ. We settle a problem of Kroening et al. [KOS+11] in the affirmative, by showing that the linearity problem for both regular and ω-regular specifications (provided as finite automata and Buchi automata respectively) is PSPACE-complete. Moreover, we establish the following dichotomies: for regular specifications, completeness thresholds are either linear or exponential, whereas for ω-regular specifications, completeness thresholds are either linear or at least quadratic in the recurrence diameter of the model under consideration. Given a formula in a temporal logic such as LTL or MTL, a fundamental problem underpinning automata-based model checking is the complexity of evaluating the formula on a given finite word. For LTL, the complexity of this task was recently shown to be in NC [KF09]. In the second part of the thesis we present an NC algorithm for MTL, a quantitative (or metric) extension of LTL, and give an AC1 algorithm for UTL, the unary fragment of LTL. We then establish a connection between LTL path checking and planar circuits which, among others, implies that the complexity of LTL path checking depends on the Boolean connectives allowed: adding Boolean exclusive or yields a temporal logic with P-complete path-checking problem. In the third part of the thesis we study the decidability of the reachability problem for parametric timed automata. The problem was introduced over 20 years ago by Alur, Henzinger, and Vardi [AHV93]. It is known that for three or more parametric clocks the problem is undecidable. We translate the problem to reachability questions in certain extensions of parametric one-counter machines. By further reducing to satisfiability in Presburger arithmetic with divisibility, we obtain decidability results for several classes of parametric one-counter machines. As a corollary, we show that, in the case of a single parametric clock (with arbitrarily many nonparametric clocks) the reachability problem is NEXP-complete, improving the nonelementary decision procedure of Alur et al. The case of two parametric clocks is open. Here, we show that the reachability is decidable in this case of automata with a single parameter.
48
Luukkainen, Matti. "A process algebraic reduction strategy for automata theoretic verification of untimed and timed concurrent systems." Helsinki : University of Helsinki, 2003. http://ethesis.helsinki.fi/julkaisut/mat/tieto/vk/luukkainen/.
Full text
49
Schmidt, Jana A. [Verfasser], Burkhard [Akademischer Betreuer] Rost, and Stefan [Akademischer Betreuer] Kramer. "Machine Learning of Timed Automata / Jana A. Schmidt. Gutachter: Burkhard Rost ; Stefan Kramer. Betreuer: Burkhard Rost." München : Universitätsbibliothek der TU München, 2013. http://d-nb.info/1046404865/34.
Full text
50
Gerke, Michael [Verfasser]. "Modeling and verifying the FlexRay physical layer protocol with reachability checking of timed automata / Michael Gerke." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2020. http://d-nb.info/1229436014/34.
Full text