Synthesis of orchestrators from service choreographies

With service interaction modelling, it is customary to distinguish between two types of models: choreographies and orchestrations. A choreography describes interactions within a collection of services from a global perspective, where no service plays a privileged role. Instead, services interact in a peer-to-peer manner. In contrast, an orchestration describes the interactions between one particular service, the orchestrator, and a number of partner services. The main proposition of this work is an approach to bridge these two modelling viewpoints by synthesising orchestrators from choreographies. To start with, choreographies are defined using a simple behaviour description language based on communicating finite state machines. From such a model, orchestrators are initially synthesised in the form of state machines. It turns out that state machines are not suitable for orchestration modelling, because orchestrators generally need to engage in concurrent interactions. To address this issue, a technique is proposed to transform state machines into process models in the Business Process Modelling Notation (BPMN). Orchestrations represented in BPMN can then be augmented with additional business logic to achieve value-adding mediation. In addition, techniques exist for refining BPMN models into executable process definitions. The transformation from state machines to BPMN relies on Petri nets as an intermediary representation and leverages techniques from theory of regions to identify concurrency in the initial Petri net. Once concurrency has been identified, the resulting Petri net is transformed into a BPMN model. The original contributions of this work are: an algorithm to synthesise orchestrators from choreographies and a rules-based transformation from Petri nets into BPMN.

Current AI in games : a review

As the graphics race subsides and gamers grow weary of predictable and deterministic game characters, game developers must put aside their “old faithful” finite state machines and look to more advanced techniques that give the users the gaming experience they crave. The next industry breakthrough will be with characters that behave realistically and that can learn and adapt, rather than more polygons, higher resolution textures and more frames-per-second. This paper explores the various artificial intelligence techniques that are currently being used by game developers, as well as techniques that are new to the industry. The techniques covered in this paper are finite state machines, scripting, agents, flocking, fuzzy logic and fuzzy state machines decision trees, neural networks, genetic algorithms and extensible AI. This paper introduces each of these technique, explains how they can be applied to games and how commercial games are currently making use of them. Finally, the effectiveness of these techniques and their future role in the industry are evaluated.

Elements pour adapter les systemes de recherche d'information aux dyslexiques [Elements to adapt information retrieval systems to dyslexic users]

RÉSUMÉ. La prise en compte des troubles de la communication dans l’utilisation des systèmes de recherche d’information tels qu’on peut en trouver sur le Web est généralement réalisée par des interfaces utilisant des modalités n’impliquant pas la lecture et l’écriture. Peu d’applications existent pour aider l’utilisateur en difficulté dans la modalité textuelle. Nous proposons la prise en compte de la conscience phonologique pour assister l’utilisateur en difficulté d’écriture de requêtes (dysorthographie) ou de lecture de documents (dyslexie). En premier lieu un système de réécriture et d’interprétation des requêtes entrées au clavier par l’utilisateur est proposé : en s’appuyant sur les causes de la dysorthographie et sur les exemples à notre disposition, il est apparu qu’un système combinant une approche éditoriale (type correcteur orthographique) et une approche orale (système de transcription automatique) était plus approprié. En second lieu une méthode d’apprentissage automatique utilise des critères spécifiques , tels que la cohésion grapho-phonémique, pour estimer la lisibilité d’une phrase, puis d’un texte. ABSTRACT. Most applications intend to help disabled users in the information retrieval process by proposing non-textual modalities. This paper introduces specific parameters linked to phonological awareness in the textual modality. This will enhance the ability of systems to deal with orthographic issues and with the adaptation of results to the reader when for example the reader is dyslexic. We propose a phonology based sentence level rewriting system that combines spelling correction, speech synthesis and automatic speech recognition. This has been evaluated on a corpus of questions we get from dyslexic children. We propose a specific sentence readability measure that involves phonetic parameters such as grapho-phonemic cohesion. This has been learned on a corpus of reading time of sentences read by dyslexic children.

Formal network behaviour analysis using model checking

In this research we modelled computer network devices to ensure their communication behaviours meet various network standards. By modelling devices as finite-state machines and examining their properties in a range of configurations, we discovered a flaw in a common network protocol and produced a technique to improve organisations' network security against data theft.

Digital Dead Time Logic and Protection Circuitry for PWM Voltage Source Converters

Power semiconductor devices have finite turn on and turn off delays that may not be perfectly matched. In a leg of a voltage source converter, the simultaneous turn on of one device and the turn off of the complementary device will cause a DC bus shoot through, if the turn off delay is larger than the turn on delay time. To avoid this situation it is common practice to blank the two complementary devices in a leg for a small duration of time while switching, which is called dead time. This paper proposes a logic circuit for digital implementation required to control the complementary devices of a leg independently and at the same time preventing cross conduction of devices in a leg, and while providing accurate and stable dead time. This implementation is based on the concept of finite state machines. This circuit can also block improper PWM pulses to semiconductor switches and filters small pulses notches below a threshold time width as the narrow pulses do not provide any significant contribution to average pole voltage, but leads to increased switching loss. This proposed dead time logic has been implemented in a CPLD and is implemented in a protection and delay card for 3- power converters.

Learning World Models in Environments with Manifest Causal Structure

This thesis examines the problem of an autonomous agent learning a causal world model of its environment. Previous approaches to learning causal world models have concentrated on environments that are too "easy" (deterministic finite state machines) or too "hard" (containing much hidden state). We describe a new domain --- environments with manifest causal structure --- for learning. In such environments the agent has an abundance of perceptions of its environment. Specifically, it perceives almost all the relevant information it needs to understand the environment. Many environments of interest have manifest causal structure and we show that an agent can learn the manifest aspects of these environments quickly using straightforward learning techniques. We present a new algorithm to learn a rule-based causal world model from observations in the environment. The learning algorithm includes (1) a low level rule-learning algorithm that converges on a good set of specific rules, (2) a concept learning algorithm that learns concepts by finding completely correlated perceptions, and (3) an algorithm that learns general rules. In addition this thesis examines the problem of finding a good expert from a sequence of experts. Each expert has an "error rate"; we wish to find an expert with a low error rate. However, each expert's error rate and the distribution of error rates are unknown. A new expert-finding algorithm is presented and an upper bound on the expected error rate of the expert is derived.

Reconfigurable Architectures for General-Purpose Computing

General-purpose computing devices allow us to (1) customize computation after fabrication and (2) conserve area by reusing expensive active circuitry for different functions in time. We define RP-space, a restricted domain of the general-purpose architectural space focussed on reconfigurable computing architectures. Two dominant features differentiate reconfigurable from special-purpose architectures and account for most of the area overhead associated with RP devices: (1) instructions which tell the device how to behave, and (2) flexible interconnect which supports task dependent dataflow between operations. We can characterize RP-space by the allocation and structure of these resources and compare the efficiencies of architectural points across broad application characteristics. Conventional FPGAs fall at one extreme end of this space and their efficiency ranges over two orders of magnitude across the space of application characteristics. Understanding RP-space and its consequences allows us to pick the best architecture for a task and to search for more robust design points in the space. Our DPGA, a fine- grained computing device which adds small, on-chip instruction memories to FPGAs is one such design point. For typical logic applications and finite- state machines, a DPGA can implement tasks in one-third the area of a traditional FPGA. TSFPGA, a variant of the DPGA which focuses on heavily time-switched interconnect, achieves circuit densities close to the DPGA, while reducing typical physical mapping times from hours to seconds. Rigid, fabrication-time organization of instruction resources significantly narrows the range of efficiency for conventional architectures. To avoid this performance brittleness, we developed MATRIX, the first architecture to defer the binding of instruction resources until run-time, allowing the application to organize resources according to its needs. Our focus MATRIX design point is based on an array of 8-bit ALU and register-file building blocks interconnected via a byte-wide network. With today's silicon, a single chip MATRIX array can deliver over 10 Gop/s (8-bit ops). On sample image processing tasks, we show that MATRIX yields 10-20x the computational density of conventional processors. Understanding the cost structure of RP-space helps us identify these intermediate architectural points and may provide useful insight more broadly in guiding our continual search for robust and efficient general-purpose computing structures.

Fault Coverage-Driven Incremental Test Generation

In this paper, we consider a classical problem of complete test generation for deterministic finite-state machines (FSMs) in a more general setting. The first generalization is that the number of states in implementation FSMs can even be smaller than that of the specification FSM. Previous work deals only with the case when the implementation FSMs are allowed to have the same number of states as the specification FSM. This generalization provides more options to the test designer: when traditional methods trigger a test explosion for large specification machines, tests with a lower, but yet guaranteed, fault coverage can still be generated. The second generalization is that tests can be generated starting with a user-defined test suite, by incrementally extending it until the desired fault coverage is achieved. Solving the generalized test derivation problem, we formulate sufficient conditions for test suite completeness weaker than the existing ones and use them to elaborate an algorithm that can be used both for extending user-defined test suites to achieve the desired fault coverage and for test generation. We present the experimental results that indicate that the proposed algorithm allows obtaining a trade-off between the length and fault coverage of test suites.

Mapas cognitivos SODA ampliados: prescrição de um método para articular atitudes, comportamentos e seqüências cognitivas a mapas SODA

Este trabalho de tese tem por objetivo ampliar o alcance e aplicação de mapas SODA, preservando a metodologia originalmente desenvolvida. Inicialmente é realizada uma revisão do método, abordando de forma conjunta os artigos seminais, a teoria psicológica de Kelly e a teoria dos grafos; e ao final propomos uma identidade entre construtos de mapas SODA com os conhecimentos tácitos e explícitos, da gestão do conhecimento (KM). Essa sequencia introdutória é completada com uma visão de como os mapas SODA tem sido aplicado. No estágio seguinte o trabalho passa a analisar de forma crítica alguns pontos do método que dão margens a interpretações equivocadas. Sobre elas passamos a propor a aplicação de teorias, de diversos campos, tais como a teoria de means-end (Marketing), a teoria da atribuição e os conceitos de atitude (Psicologia), permitindo inferências que conduzem à proposição da primeira tese: mapas SODA são descritores de atitudes. O próximo estágio prossegue analisando criticamente o método, e foca no paradigma estabelecido por Eden, que não permite conferir ao método o status de descritor de comportamento. Propomos aqui uma mudança de paradigma, adotando a teoria da ação comunicativa, de Habermas, e sobre ela prescrevemos a teoria da ação e da escada da inferência (Action Science) e uma teoria da emoção (neuro ciência), o que permite novas inferências, que conduzem à proposição da segunda tese: mapas SODA podem descrever comportamentos. Essas teses servem de base para o alargamento de escopos do método SODA. É proposta aqui a utilização da teoria de máquinas de estado finito determinístico, designadas por autômato. Demonstramos um mapeamento entre autômato com mapas SODA, obtendo assim o autômato SODA, e sobre ele realizamos a última contribuição, uma proposta de mapas SODA hierárquicos, o que vem a possibilitar a descrição de sequencias de raciocínio, ordenando de forma determinística atitudes e comportamentos, de forma estruturada. A visão de como ela pode ser aplicada é realizada por meio de estudo de caso.

A REACHABILITY TREE FOR STATECHARTS AND ANALYSIS OF SOME PROPERTIES

Statecharts are an extension to finite state machines with capability for expressing hierarchical decomposition and parallelism. They also have a mechanism called history, to remember the last visit to a superstate. An algorithm to create a reachability tree for statecharts is presented. Also shown is how to use this tree to analyse dynamic properties of statecharts; reachability from any state configuration, usage of transitions, reinitiability, deadlocks, and valid sequence of events. Owing to its powerful notation, building a reachability tree for statecharts presents some difficulties, and we show how these problems were solved in the tree we propose.

Ferramentas para a integração de redes de Petri e VHDL na síntese de sistemas digitais

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

On reducing test length for FSMs with extra states

A long-standing problem when testing from a deterministic finite state machine is to guarantee full fault coverage even if the faults introduce extra states in the implementations. It is well known that such tests should include the sequences in a traversal set which contains all input sequences of length defined by the number of extra states. This paper suggests the SPY method, which helps reduce the length of tests by distributing sequences of the traversal set and reducing test branching. It is also demonstrated that an additional assumption about the implementation under test relaxes the requirement of the complete traversal set. The results of the experimental comparison of the proposed method with an existing method indicate that the resulting reduction can reach 40%. Experimental results suggest that the additional assumption about the implementation can help in further reducing the test suite length. Copyright (C) 2011 John Wiley & Sons, Ltd.

MODEL PARTITIONS AND COMPACT TEST CASE SUITES

We present a generalized test case generation method, called the G method. Although inspired by the W method, the G method, in contrast, allows for test case suite generation even in the absence of characterization sets for the specification models. Instead, the G method relies on knowledge about the index of certain equivalences induced at the implementation models. We show that the W method can be derived from the G method as a particular case. Moreover, we discuss some naturally occurring infinite classes of FSM models over which the G method generates test suites that are exponentially more compact than those produced by the W method.

ParTec and KarnUMa-Digital tools as a help for freshman learning

[EN]Freshman students always present lower success rates than other levels of students. Digital systems is a course usually taught at first year studentsand its success rate is not very high. In this work we introduce three digital tools to improve freshman learning designed for easy use and one of them is a tool for mobile terminals that can be used as a game. The first tool is ParTec and is used to implement and test the partition technique. This technique is used to eliminate redundant states in finite state machines. This is a repetitive task that students do not like to perform. The second tool is called KarnUMa and is used for simplifying logic functions through Karnaugh Maps. Simplifying logical functions is a core task for this course and although students usually perform this task better than other tasks, it can still be improved. The third tool is a version of KarnUMa, designed for mobile devices. All the tools are available online for download and have been a helpful tool for students.

A component library to improve the reusability in the development of converged services

The evolution of communications networks to Next Generation Networks (NGN) has encouraged the development of new services. Nowadays, several technologies are being integrated into telecommunications services in order to provide new functionalities, resulting in what are known as converged services. The objective is to adapt the behavior of the services to the necessities of different users, generating customized services. Some of the main technologies involved in their development are those related to the Web. But due to this type of services implies the combination of different technologies, their development is a very complex process that has to be improved to reduce the time and cost required, with the aim of promoting the success of such services. This paper proposes to apply software reuse through the utilization of a component library and presents one focused on ECharts for SIP Servlets (E4SS). It is a framework, based on the SIP Servlet specification, which uses finite state machines for the definition of converged communications services. Also, to promote the use of the library, a methodology is proposed in order to facilitate the integration between the library operations and the software development cycle.