A Graphical User Interface (GUI) is defined by its appearance and its behavior. A GUI’s behavior determines how it reacts to user and system events such as mouse, keyboard, or touchscreen presses, or changes to an underlying data model. Although many tools are effective in enabling designers to specify a GUI’s appearance, defining a custom behavior is difficult and error-prone. Many of the difficulties developers face in defining GUI behaviors are the result of their reactive nature. The order in which GUI code is executed depends upon the order in which it receives external inputs. Most widely used user interface programming frameworks use an event-callback model, where developers define GUI behavior by defining callbacks—sequences of low-level actions—to take in reaction to events. However, the event-callback model for user-interface development has several problems, many of which have been identified long before I started work on this dissertation. First, it is disorganized: the location and order of event-callback code often has little correspondence with the order in which it will be executed. Second, it divides GUI code in a way that requires writing interdependent code to keep the interface in a consistent state. This is because maintaining a consistent state requires referencing and modifying the same state variables across multiple different callbacks, which are often distributed throughout the code. In this dissertation, I will introduce a new framework for defining GUI behavior, called the stateconstraint framework. This framework combines constraints—which allow developers to define relationships among interface elements that are automatically maintained by the system—and state machines—which track the status of an interface. In the state-constraint framework, developers write GUI behavior by defining constraints that are enforced when the interface is in specific states. This framework allows developers to specify more nuanced constraints and allows the GUI’s appearance and behavior to vary by state. I created two tools using the state-constraint framework: a library for Web developers (ConstraintJS) and an interactive graphical language (InterState). ConstraintJS provides constraints that can be used both to control content and control display, and integrates these constraints with the three Web languages—HTML, CSS, and JavaScript. ConstraintJS is designed to take advantage of the declarative syntaxes of HTML and CSS: It allows the majority of an interactive behavior to be expressed concisely in HTML and CSS, rather than requiring the programmer to write large amounts of JavaScript. InterState introduces a visual notation and live editor to clearly represent how states and constraints combine to define GUI behavior. An evaluation of InterState showed that its computational model, visual notation, and editor were effective in allowing developers to define GUI behavior compared to conventional event-callback code. InterState also introduces extensions to the state-constraint framework to allow developers to easily re-use behaviors and primitives for authoring multi-touch gestures.

This dissertation is concerned with finite state machine-based technology for modeling natural language. Finite-state machines have proven to be efficient computational devices in modeling natural language phenomena in morphology and phonology. Because of their mathematical closure properties, finite-state machines can be manipulated and combined in many flexible ways that closely resemble formalisms used in different areas of linguistics to describe natural language. The use of finite-state transducers in constructing natural language parsers and generators has proven to be a versatile approach to describing phonological alternation, morphological constraints and morphotactics, and syntactic phenomena on the phrase level.The main contributions of this dissertation are the development of a new model of multitape automata, the development of a new logic formalism that can substitute for regular expressions in constructing complex automata, and adaptations of these techniques to solving classical construction problems relating to finite-state transducers, such as modeling reduplication and complex phonological replacement rules.The multitape model presented here goes hand-in-hand with the logic formalism, the latter being a necessary step to constructing the former. These multitape automata can then be used to create entire morphological and phonological grammars, and can also serve as a neutral intermediate tool to ease the construction of automata for other purposes.The construction of large-scale finite-state models for natural language grammars is a very delicate process. Making any solution practicable requires great care in the efficient implementation of low-level tasks such as converting regular expressions, logical statements, sets of constraints, and replacement rules to automata or finite transducers. To support the overall endeavor of showing the practicability of the logical and multitape extensions proposed in this thesis, a detailed treatment of efficient implementation of finite-state construction algorithms for natural language purposes is also presented.

O TESTE baseado em modelos visa a possibilitar a derivação de conjuntos de casos de teste a partir de especificações formais, tais como Máquinas de Estados Finitos. Os conjuntos de teste podem ser obtidos tanto pelos métodos clássicos de geração quanto por alguma abordagem ad hoc. Procura-se obter um conjunto de teste que consiga detectar todos os possíveis defeitos de uma implementação e possua tamanho reduzido para que a sua aplicação seja factível. Por questões de ordem prática, pode não ser possível a aplicação de todo o conjunto de teste gerado. Desse modo, um subconjunto de casos de teste deve ser selecionado, ou seja, uma minimização do conjunto de teste deve ser realizada. No entanto, é fundamental que a minimização reduza o custo de aplicação dos testes, mas mantenha a efetividade em revelar defeitos. Neste trabalho, propõe-se um algoritmo de minimização de conjuntos de teste para Máquinas de Estados Finitos. O algoritmo baseia-se em condições de suficiência para que a completude em relação à detecção de defeitos seja mantida. O algoritmo foi utilizado em dois diferentes contextos. Utilizou-se o algoritmo com conjuntos de teste gerados de forma aleatória para verificar a minimização obtida. O algoritmo também foi utilizado para reduzir o esforço em se obter um conjunto completo em relação à detecção de defeitos / THE Model-based testing aims at generating test suites from formal specifications, such as Finite State Machines. Test suites can be obtained either from classical test derivation methods or from some ad-hoc approach. It is desirable to produce a test suite which detects all possible faults of an implementation and has small size, so that its application can be feasible. For practical reasons, the application of the generated test suite may not be possible. Therefore, a subset of test cases should be selected, i.e., a test suite minimization should be performed. However, it is important that the minimization reduces the test application cost, but keeps the effectiveness in revealing faults. In this work, an algorithm is proposed for the minimization of test suites generated from Finite State Machines. The algorithm is based on sufficient conditions, so that test suite completeness can be maintained. The algorithm was used in two different contexts. It was used with randomly generated test suites to verify the minimization obtained. The algorithm was also used to reduce the effort of obtaining a test suite with full fault coverage

O teste baseado em modelos visa à derivação de casos de teste a partir de modelos produzidos ao longo do desenvolvimento de software. Nesse contexto, as Máquinas de Estados Finitos têm sido amplamente pesquisadas e utilizadas para derivação de seqüências de teste. Para isso, vários métodos de geração de seqüências de teste têm sido desenvolvidos há várias décadas. O objetivo desses métodos é a obtenção de um conjunto de teste que seja capaz de revelar os defeitos de uma implementação. Entretanto, muitas vezes os conjuntos gerados são muito grandes, o que torna sua aplicação inviável. Trabalhos recentes definiram condições que podem ser utilizadas para investigar mecanismos de redução de casos de teste. Este trabalho apresenta uma estratégia para a redução de conjuntos de seqüências de teste a partir de Máquinas de Estados Finitos com base em condições de suficiência. A estratégia baseia-se na combinação de seqüências de um conjunto de teste, de forma a reduzir o número de seqüências e o tamanho delas, mantendo a completude do conjunto. São apresentadas seis abordagens de redução baseadas na estratégia proposta, as quais foram implementadas em uma ferramenta. Para avaliar as abordagens foram conduzidos estudos experimentais, os quais também serviram para inferir sobre as características e propriedades de cada abordagem. Além disso, um estudo de caso com MEFs reais também foi realizado / Model-based testing aims at generating test cases from models produced along the software development process. In this context, Finite State Machines (FSM) have been largely investigated and used for generating test sequences. In the past decades, several test generation methods have been proposed to obtain test suites that are able to reveal implementation faults. Nevertheless, most of the generated test suites are huge, thus hindering their application in practice. Recent research has defined new sufficient conditions that can be employed in mechanisms for reducing the length of test sequences. This work presents a strategy based on sufficient conditions for reducing the length of test cases derived from FSMs. Our strategy is based on sequence combination of a test suite, aiming to reduce the number of sequences and their length, however still keeping full fault coverage. Six reduction approaches are presented based on the proposed strategy and implemented in a tool. In order to evaluate the strategy, we conducted experimental studies that identified characteristics and properties for each of the six proposed approaches. Moreover, a case study with real-world FSMs was performed

The way our brain works is still an open question, but one thing seems to be clear: biological neural systems are computationally powerful, robust and noisy. Natural nervous system are able to control limbs in different scenarios with high precision. As neural networks in living beings communicate through spikes, modern neuromorphic systems try to mimic them by using spike-based neuron models. This thesis is focused on the advancement of neurorobotics or brain inspired robotic arm controllers based on artificial neural network architectures. The architecture chosen to implement those controllers was the spike neuron version of Reservoir Computing framework, called Liquid State Machines. The main goal is to explore the possibility of using brain inspired neural networks to control a robot by demonstration. Moreover, it aims to achieve systems robust to environmental noise and internal structure destruction presenting a graceful degradation. As the validation, a series of action learning experiments are presented where simulated robotic arms are controlled. The investigation starts with a 2 degrees of freedom arm and moves to the research version of the Rethink Robotics Inc. collaborative humanoid robot Baxter. Moreover, a proof-of- concept experiment is also done using the real Baxter robot. The results show Liquid State Machines, when endowed with an extra external feedback loop, can be also employed to control more complex humanoid robotic arms than a simple planar 2 degrees of freedom one. Additionally, the new parallel architecture presented here was capable to withstand noise and internal destruction better than a simple use of multiple columns also presenting a graceful degradation behaviour.

O TESTE baseado em modelos visa a possibilitar a derivação de conjuntos de casos de teste a partir de especificações formais, tais como Máquinas de Estados Finitos. Os conjuntos de teste podem ser obtidos tanto pelos métodos clássicos de geração quanto por alguma abordagem ad hoc. Procura-se obter um conjunto de teste que consiga detectar todos os possíveis defeitos de uma implementação e possua tamanho reduzido para que a sua aplicação seja factível. Por questões de ordem prática, pode não ser possível a aplicação de todo o conjunto de teste gerado. Desse modo, um subconjunto de casos de teste deve ser selecionado, ou seja, uma minimização do conjunto de teste deve ser realizada. No entanto, é fundamental que a minimização reduza o custo de aplicação dos testes, mas mantenha a efetividade em revelar defeitos. Neste trabalho, propõe-se um algoritmo de minimização de conjuntos de teste para Máquinas de Estados Finitos. O algoritmo baseia-se em condições de suficiência para que a completude em relação à detecção de defeitos seja mantida. O algoritmo foi utilizado em dois diferentes contextos. Utilizou-se o algoritmo com conjuntos de teste gerados de forma aleatória para verificar a minimização obtida. O algoritmo também foi utilizado para reduzir o esforço em se obter um conjunto completo em relação à detecção de defeitos / THE Model-based testing aims at generating test suites from formal specifications, such as Finite State Machines. Test suites can be obtained either from classical test derivation methods or from some ad-hoc approach. It is desirable to produce a test suite which detects all possible faults of an implementation and has small size, so that its application can be feasible. For practical reasons, the application of the generated test suite may not be possible. Therefore, a subset of test cases should be selected, i.e., a test suite minimization should be performed. However, it is important that the minimization reduces the test application cost, but keeps the effectiveness in revealing faults. In this work, an algorithm is proposed for the minimization of test suites generated from Finite State Machines. The algorithm is based on sufficient conditions, so that test suite completeness can be maintained. The algorithm was used in two different contexts. It was used with randomly generated test suites to verify the minimization obtained. The algorithm was also used to reduce the effort of obtaining a test suite with full fault coverage

Distributed systems are rapidly increasing in importance due to the need for scalable computations on huge volumes of data. This fact is reflected in many real-world distributed applications such as Amazon's EC2 cloud computing service, Facebook's Cassandra key-value store or Apache's Hadoop MapReduce framework. Multi-core architectures developed by companies such as Intel and AMD have further brought this to prominence, since workloads can now be distributed across many individual cores. The nodes or entities in such systems are often built using commodity hardware and are prone to physical failures and security vulnerabilities. Achieving fault tolerance in such systems is a challenging task, since it is not easy to observe and control these distributed entities. Replication is a standard approach for fault tolerance in distributed systems. The main advantage of this approach is that the backups incur very little overhead in terms of the time taken for normal operation or recovery. However, replication is grossly wasteful in terms of the number of backups required for fault tolerance. The large number of backups has two major implications. First, the total space or memory required for fault tolerance is considerably high. Second, there is a significant cost of resources such as the power required to run the backup processes. Given the large number of distributed servers employed in real-world applications, it is a hard task to provide fault tolerance while achieving both space and operational efficiency. In the world of data fault tolerance and communication, coding theory is used as the space efficient alternate for replication. A direct application of coding theory to distributed servers, treating the servers as blocks of data, is very inefficient in terms of the updates to the backups. This is primarily because each update to the server will affect many blocks in memory, all of which have to be re-encoded at the backups. This leads us to the following thesis statement: Can we design a mechanism for fault tolerance in distributed systems that combines the space efficiency of coding theory with the low operational overhead of replication? We present a new paradigm to solve this problem, broadly referred to as fusion. We provide fusion-based solutions for two models of computation that are representative of a large class of applications: (i) Systems modeled as deterministic finite state machines and, (ii) Systems modeled as programs containing data structures. For finite state machines, we use the notion of Hamming distances to present a polynomial time algorithm to generate efficient backup state machines. For programs hosting data structures, we use a combination of erasure codes and selective replication to generate efficient backups for most commonly used data structures such as queues, array lists, linked lists, vectors and maps. We present theoretical and experimental results that demonstrate the efficiency of our schemes over replication. Finally, we use our schemes to design an efficient solution for fault tolerance in two real-world applications: Amazons Dynamo key-value store, and Google's MapReduce framework. / text

Web services provide means to computerize e-business processes. To be able to satisfy business requirements web services must be developed rapidly and in high quality. Code generation techniques are frequently employed. In such context, verification of web service models emerges as a relevant issue: model verification makes it easier to detect and remove errors of system specification at the early stages of software development cycle. Available model verification tools require transformation of the objective model into complex formal notations, supported by the tool. It would be convenient to implement model verification directly in a CASE tool. This thesis describes a method for checking web service models based on verification of UML state machines. Conceptual algorithms for checking state machine’s safety criteria: reachability, completeness and consistency are provided. These algorithms, implemented in CASE tools could help to ensure the correctness and consistency of behavioral models. Also, a state machine template for composite web services is presented. Template complements state machine with transitions representing unsuccessful scenarios. Designer is freed from necessity to repeat reoccurring unsuccessful transitions for every event. This template is useful for automatic code generation.

This dissertation explores the problem of energy estimation in supervised Non-Intrusive Load Monitoring (NILM). NILM refers to a set of techniques used to estimate the electricity consumed by individual loads in a building from measurements of the total electrical consumption. Most commonly, NILM works by first attributing any significant change in the total power consumption (also known as an event) to a specific load and subsequently using these attributions (i.e. the labels for the events) to estimate energy for each load. For this last step, most proposed solutions in the field impart simplifying assumptions to make the problem more tractable. This has severely limited the practicality of the proposed solutions. To address this knowledge gap, we present a framework for creating appliance models based on classification labels and aggregate power measurements that can help relax many of these assumptions. Within the framework, we model the problem of utilizing a sequence of event labels to generate energy estimates as a broader class of problems that has two major components (i) With the understanding that the labels arise from a process with distinct states and state transitions, we estimate the underlying Finite State Machine (FSM) model that most likely generated the observed sequence (ii) We allow for the observed sequence to have errors, and present an error correction algorithm to detect and correct them. We test the framework on data from 43 appliances collected from 19 houses and find that it improves errors in energy estimates when compared to the case with no correction in 19 appliances by a factor of 50, leaves 17 appliances unchanged, and negatively impacts 6 appliances by a factor of 1.4. This approach of utilizing event sequences to estimate energy has implications in virtual metering of appliances as well. In a case study, we utilize this framework in order to substitute the need of plug-level sensors with cheap and easily deployable contacless sensors, and find that on the 6 appliances virtually metered using magnetic field sensors, the inferred energy values have an average error of 10:9%.

O teste baseado em modelos visa à derivação de casos de teste a partir de modelos produzidos ao longo do desenvolvimento de software. Nesse contexto, as Máquinas de Estados Finitos têm sido amplamente pesquisadas e utilizadas para derivação de seqüências de teste. Para isso, vários métodos de geração de seqüências de teste têm sido desenvolvidos há várias décadas. O objetivo desses métodos é a obtenção de um conjunto de teste que seja capaz de revelar os defeitos de uma implementação. Entretanto, muitas vezes os conjuntos gerados são muito grandes, o que torna sua aplicação inviável. Trabalhos recentes definiram condições que podem ser utilizadas para investigar mecanismos de redução de casos de teste. Este trabalho apresenta uma estratégia para a redução de conjuntos de seqüências de teste a partir de Máquinas de Estados Finitos com base em condições de suficiência. A estratégia baseia-se na combinação de seqüências de um conjunto de teste, de forma a reduzir o número de seqüências e o tamanho delas, mantendo a completude do conjunto. São apresentadas seis abordagens de redução baseadas na estratégia proposta, as quais foram implementadas em uma ferramenta. Para avaliar as abordagens foram conduzidos estudos experimentais, os quais também serviram para inferir sobre as características e propriedades de cada abordagem. Além disso, um estudo de caso com MEFs reais também foi realizado / Model-based testing aims at generating test cases from models produced along the software development process. In this context, Finite State Machines (FSM) have been largely investigated and used for generating test sequences. In the past decades, several test generation methods have been proposed to obtain test suites that are able to reveal implementation faults. Nevertheless, most of the generated test suites are huge, thus hindering their application in practice. Recent research has defined new sufficient conditions that can be employed in mechanisms for reducing the length of test sequences. This work presents a strategy based on sufficient conditions for reducing the length of test cases derived from FSMs. Our strategy is based on sequence combination of a test suite, aiming to reduce the number of sequences and their length, however still keeping full fault coverage. Six reduction approaches are presented based on the proposed strategy and implemented in a tool. In order to evaluate the strategy, we conducted experimental studies that identified characteristics and properties for each of the six proposed approaches. Moreover, a case study with real-world FSMs was performed