Thesis (M. Phil.)--University of Hong Kong, 1994. / Includes bibliographical references (leaves 99-102).

Thesis (M. Sc.), Memorial University of Newfoundland, 1998. / Bibliography: leaves 63-67.

The aggregation hierarchy is one of the most significant data abstraction mechanisms that emerged as a result to semantic extensions to traditional systems analysis and design methods. The way inheritance works in this hierarchy is studied in this thesis. Special emphasis is placed on the behaviour of objects which are related via an aggregation hierarchy. A framework is introduced for capturing the behaviour of a system from the respective behaviour(s) of its components. This framework is based on a 3-level behaviour modelling hierarchy. One of the most significant contributions of this framework is the ability to apply inter-object interactions when building a behaviour model of a system. These interactions are significant in that they can yield totally distinct models of the systems functionality. Some of the notions that are supported by the behaviour modelling framework include unreachable and transient states, transition chains (cascades) and concurrency. The framework also enables the creation of behaviour model (semantic) hierarchies, wherein certain facets of the systems behaviour or functionality can be hidden (abstracted out) in a gradual fashion that suits the requirements of the problem domain. This creates what is effectively, distinct views of the behaviour or functionality of the system. The notions and concepts that are introduced here are verified and presented in a comprehensive case study that shows what can be achieved using these ideas. Suggestions are also made for future work which can help overcome some of the limitations introduced throughout this research.

Coloured Petri nets (CPN) are an extension of a standard place-transition Petri nets (P/T PN). Every token and place have its type (and eventually a value) and various inscriptions can be inserted into the net. CPN excel with great readibility and expresivity. At the same time, they carry a well-defined formal basis, which eases its computer simulation and allows limited verification of certain attributes to be performed. Motivation for doing this project is the simple fact that currently only one public software tool is available for CPN creation and simulation - CPNTools developed on the Aarhus university. The program, however, is quite complicated and hard to handle for an unexperienced user. The goal is to research capabilities and properties of both CPNs and CPNTools and on this basis design and implement a didactic application with swift and intuitive interface that helps users without deeper theoretical insight to get a grasp of the problematics.

Le test d’identification d’état d’un système à événement discret (SED) a pour but d’en identifier l’état final, lorsque son état initial est inconnu. Une solution classique à ce problème, en supposant que le SED n’ait pas de sorties observables, consiste à déterminer une séquences de synchronisation, c.à-d., une séquence d’événements d’entrée qui conduit le SED sur un état connu. Ce problème a été résolu dans les années 60’ à l’aide des automates. L’objectif principal de cette thèse est d’utiliser les réseaux de Petri (RdP) pour obtenir une résolution plus optimal de ce problème et pour une plus large classe de systèmes.Initialement, nous montrons que la méthode classique peut être aisément étendue aux RdP synchronisés. Pour cette classe de réseaux non-autonomes, toute transition est associée à un événement d’entrée.L’approche proposée est générale, dans la mesure où elle s’applique à des RdP bornés arbitraires. Cependant, elle engendre le problème d’explosion combinatoire du nombre d’états. Pour obtenir des meilleures solutions, nous considérons une classe spéciale de RdP : les graphes d’état (GdE). Pour ces réseaux, nous considérons d’abord les GdE fortement connexes et proposons des approches pour la construction de SS, qui exploitent les propriétés structurelles du réseau en évitant ainsi une énumération exhaustive de l’espace d’état. Ces résultats s’étendent aux GdE non fortement connexes et à tout RdP synchronisé composé de GdE. Enfin, nous considérons la classe des RdP non bornés et proposons des séquences qui synchronisent le marquage des places non bornées. Une boîte à outils fournit toutes les approches décrites et est appliquée à des différents bancs d’essai. / State-identification experiments are designed to identify the final state of a discrete event system (DES) when its initial state is unknown. A classical solution, assuming the DES has no observable outputs, consists in determining a synchronizing sequence (SS), i.e., a sequence of input events that drives the system to a known state. This problem was essentially solved in the 60’ using automata. The main objective of this thesis is to use Petri nets (PNs) for solving the state-identification problem more efficiently and for a wider class of systems.We start showing that the classical SS construction method based on automata can be easily applied to synchronized PNs, a class of non-autonomous nets where each transition is associated with an input event. The proposed approach is fairly general and it works for arbitrary bounded nets with a complexity that is polynomial with the size of the state space. However, it incurs in the state-space explosion problem.Looking for more efficient solutions, we begin by considering a subclass of PNs called state machines (SMs). We first consider strongly connected SMs and propose a framework for SS construction that exploits structural criteria, not requiring an exhaustive enumeration of the state space of the net. Results are further extended to larger classes of nets, namely non strongly connected SMs and nets containing SM subnets. Finally we consider the class of unbounded nets that describe infinite state systems: even in this case we are able to compute sequences to synchronize the marking of bounded places. A Matlab toolbox implementing all approaches previously described has been designed and applied to a series of benchmarks.

Finding integer solutions to linear equations has various real world applications. In the thesis, we investigate its application to the reachability analysis of Petri nets. Introduced by Petri in 1962, Petri net has been a powerful mathematical formalism for modeling, analyzing and designing discrete event systems. In the research community of Petri nets, finding a feasible path from the initial state to the target state in Petri net, known as reachability analysis, is probably one of the most important and challenging subjects. The reachability algebraic analysis is equivalent to finding the nonnegative integer solutions to a fundamental equation constructed from the Petri net. We apply our algorithm in this thesis to reachability analysis of Petri net by finding the nonnegative integer solutions to the fundamental equation. / Finding the optimal binary solution to a quadratic object function is known as the Binary Quadratic Programming problem (BQP), which has been studied extensively in the last three decades. In this thesis, by investigating geometric features of the ellipse contour of a concave quadratic function, we derive new upper and lower bounding methods for BQP. Integrating these new bounding schemes into a proposed solution algorithm of a branch-and-bound type, we propose an exact solution method in solving general BQP with promising preliminary computational results. Meanwhile, by investigating some special structures of the second order matrix and linear term in BQP, several polynomial time algorithms are discussed to solve some special cases of BQP. / In the realm of integer programming, finding integer solutions to linear equations is another important research direction. The problem is proved to be NP-Complete, and several algorithms have been proposed such as the algorithm based on linear Diophantine equations as well as the method based on Groebner bases. Unlike the traditional algorithms, the new efficient method we propose in this thesis is based on our results on zero duality gap and the cell enumeration of an arrangement of hyperplanes in discrete geometry. / Integer programming plays an important role in operations research and has a wide range of applications in various fields. There are a lot of research directions in the area of integer programming. In this thesis, two main topics will be investigated in details. One is to find the optimal binary solution to a quadratic object function, and the other is to find integer solutions to linear equations. / Gu, Shenshen. / Adviser: Wang Jun. / Source: Dissertation Abstracts International, Volume: 73-01, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 98-103). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

A telepresença, como um refinamento da teleoperação, permite que o indivíduo controle não apenas a simulação mas a própria realidade. Uma vez que, esta proporciona a habilidade de manipular a realidade física remotamente em tempo real, através de sua representação virtual. Através da tecnologia de realidade virtual, pode-se criar uma grande diversidade de ambientes apropriados aos mais variados tipos de aplicações, possibilitando simulações de situações do mundo real em um ambiente ou mundo virtual. A aplicação de ambientes virtuais no processo de manufatura está relacionada tanto com a manutenção e treinamento, como também a criação e simulação de protótipos virtuais antes de sua utilização no chão-de-fábrica. O uso de redes de Petri para modelagem de ambientes virtuais, mostra-se como uma poderosa ferramenta gráfica/matemática que pode capturar naturalmente as principais características dos sistemas de realidade virtual, além de proporcionar resultados empíricos interessantes na verificação automática de concorrência e sistemas de tempo real. Por permitir modelar a computação não determinística e paralela, a modelagem de ambientes virtuais com redes de Petri é adequada não apenas para simulação, verificação e validação desses sistemas, mas para o próprio controle dos ambientes modelados. Ao associar os elementos de uma rede de Petri com os elementos do paradigma orientado à objetos de um conjunto de classes que constituem os objetos que irão compor os ambientes virtuais e os sistemas de telepresença, obtém-se uma valiosa ferramenta para o controle dos métodos dos objetos virtuais e reais a serem invocados. O objetivo deste trabalho é o desenvolvimento do modo de associação de redes de Petri com objetos virtuais e reais para controle de ambientes virtuais imersivos e telepresença, com base na descrição de um sistema de autoria de telepresença com controle em RP. Os resultados obtidos trarão avanços quanto ao desenvolvimento e implantação de aplicações de manufatura virtual em um ambiente de visualização 3D imersivo. / The telepresence, as a refinement of teleoperation, allows the individual not only to control the simulation but also the own reality. Since this provides the ability to manipulate the physical reality remotely in real time, through its virtual representation. Through the technology of virtual reality, one can create a wide variety of environments suitable for all kinds of applications, enabling simulations of the situations in a real world environment or virtual world. The application of virtual environments in the manufacturing process is related to both the maintenance and training, and also the creation and simulation of virtual prototypes before their use in the shop-floor. The use of Petri nets for modeling virtual environments, shows itself as a powerful graphics/mathematics tool that can capture the main features of virtual reality systems, as well as offering interesting empirical results in automatic verification of concurrence and real time systems. By allowing to model non-deterministic and parallel computation, modeling of virtual environments with Petri nets is appropriate not only for simulation, verification and validation of these systems, but also for controlling the environments modeled. By associating the elements of a Petri net with the elements of the object oriented paradigm of a set of classes that are the objects that will compose the virtual environments and telepresence systems, one gets a valuable tool for controlling of the methods of virtual and real objects to be invoked. The objective of this work is the development of the mode of association of Petri nets with virtual and real objects for controlling immersive virtual environments and telepresence, based on the description of a telepresence authoring system controlled by PN. The results will bring progress on the development and deployment of virtual manufacturing applications in an immersive 3D visualization environment.

A telepresença, como um refinamento da teleoperação, permite que o indivíduo controle não apenas a simulação mas a própria realidade. Uma vez que, esta proporciona a habilidade de manipular a realidade física remotamente em tempo real, através de sua representação virtual. Através da tecnologia de realidade virtual, pode-se criar uma grande diversidade de ambientes apropriados aos mais variados tipos de aplicações, possibilitando simulações de situações do mundo real em um ambiente ou mundo virtual. A aplicação de ambientes virtuais no processo de manufatura está relacionada tanto com a manutenção e treinamento, como também a criação e simulação de protótipos virtuais antes de sua utilização no chão-de-fábrica. O uso de redes de Petri para modelagem de ambientes virtuais, mostra-se como uma poderosa ferramenta gráfica/matemática que pode capturar naturalmente as principais características dos sistemas de realidade virtual, além de proporcionar resultados empíricos interessantes na verificação automática de concorrência e sistemas de tempo real. Por permitir modelar a computação não determinística e paralela, a modelagem de ambientes virtuais com redes de Petri é adequada não apenas para simulação, verificação e validação desses sistemas, mas para o próprio controle dos ambientes modelados. Ao associar os elementos de uma rede de Petri com os elementos do paradigma orientado à objetos de um conjunto de classes que constituem os objetos que irão compor os ambientes virtuais e os sistemas de telepresença, obtém-se uma valiosa ferramenta para o controle dos métodos dos objetos virtuais e reais a serem invocados. O objetivo deste trabalho é o desenvolvimento do modo de associação de redes de Petri com objetos virtuais e reais para controle de ambientes virtuais imersivos e telepresença, com base na descrição de um sistema de autoria de telepresença com controle em RP. Os resultados obtidos trarão avanços quanto ao desenvolvimento e implantação de aplicações de manufatura virtual em um ambiente de visualização 3D imersivo. / The telepresence, as a refinement of teleoperation, allows the individual not only to control the simulation but also the own reality. Since this provides the ability to manipulate the physical reality remotely in real time, through its virtual representation. Through the technology of virtual reality, one can create a wide variety of environments suitable for all kinds of applications, enabling simulations of the situations in a real world environment or virtual world. The application of virtual environments in the manufacturing process is related to both the maintenance and training, and also the creation and simulation of virtual prototypes before their use in the shop-floor. The use of Petri nets for modeling virtual environments, shows itself as a powerful graphics/mathematics tool that can capture the main features of virtual reality systems, as well as offering interesting empirical results in automatic verification of concurrence and real time systems. By allowing to model non-deterministic and parallel computation, modeling of virtual environments with Petri nets is appropriate not only for simulation, verification and validation of these systems, but also for controlling the environments modeled. By associating the elements of a Petri net with the elements of the object oriented paradigm of a set of classes that are the objects that will compose the virtual environments and telepresence systems, one gets a valuable tool for controlling of the methods of virtual and real objects to be invoked. The objective of this work is the development of the mode of association of Petri nets with virtual and real objects for controlling immersive virtual environments and telepresence, based on the description of a telepresence authoring system controlled by PN. The results will bring progress on the development and deployment of virtual manufacturing applications in an immersive 3D visualization environment.

Cette thèse s'intéresse à la vérification de systèmes automatisables par model-checking. La question sous-jacente autour de laquelle se construit la contribution est la recherche d'un compromis entre différents objectifs potentiellement contradictoires : la décidabilité des systèmes à vérifier, l'expressivité des formalismes de modélisation, l'efficacité de la vérification, et la certification des outils utilisés. Dans ce but, on choisit de baser la modélisation sur des réseaux de Petri annotés par des langages de programmation réels. Cela implique la semi-décidabilité de la plupart des questions puisque la responsabilité de la terminaison est remise entre les mains du modélisateur (tout comme la terminaison des programmes est de la responsabilité du programmeur). Afin d'exploiter efficacement ces annotations, on choisit ensuite une approche de compilation de modèle qui permet de générer des programmes efficaces dans le langage des annotations, qui sont alors exécutées de la manière la plus efficace. De plus, la compilation est optimisée en tirant partie des spécificités de chaque modèle et nous utilisons l'approche de model-checking explicite qui autorise cette richesse d'annotations tout en facilitant le diagnostique et en restant compatible avec la simulation (les modèles compilés peuvent servir à de la simulation efficace). Enfin, pour combattre l'explosion combinatoire, nous utilisons des techniques de réductions de symétries qui permettent de réduire les temps d'exploration et l'espace mémoire nécessaire. / This work focuses on verification of automated systems using model-checking techniques. We focus on a compromise between potentially contradictory goals: decidability of systems to be verified, expressivity of modeling formalisms, efficiency of verification, and certification of used tools. To do so, we use high level Petri nets annotated by real programming languages. This implies the semi-decidability of most of problems because termination is left to the modeler (like termination of programs is left to the programmer). To handle these models, we choose a compilation approach which produces programs in the model annotation language, this allows to execute them efficiently. Moreover, this compilation is optimizing using model peculiarities. However, this rich expressivity leads to the use of explicit model-checking which allows to have rich model annotations but also allows to easily recover errors from verification, and remains compatible with simulation (these compiled models can be used for efficient simulation). Finally, to tackle the state space explosion problem, we use reduction by symmetries techniques which allow to reduce exploration times and state spaces.

Thesis (M.S.)--University of Missouri--Rolla, 2007. / Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed November 30, 2007) Includes bibliographical references (p. 199-209).