Computational modeling of part relations of shapes is a challenging problem that has been addressed by many researchers since sixties. The most important source of the difficulty is the continuous nature of shapes, which makes the expression of shape very difficult in terms of discrete parts. When discrete parts are combined, they fuse and yield new parts, i.e. parts emerge. There is a number of methods that support emergent part detection. However all of these methods are based on strong assumptions in terms of what constitute a part. There is a need for a generic solution that treats a shape independently of any restriction resulting from analytical, geometrical, or logical abstractions. To this end, we have developed two novel strategies, which can be used both separately and jointly. Both strategies are relatable to the algebraic formalization of shape grammars (by Stiny). In the course of this thesis work, we have introduced a novel data structure called Over-Complete Graph to address the problem of part embedding in the existence of discrete registration marks / and we have developed a novel and robust method for the automatic selection of registration marks. Both developments are certainly useful for other visual problems. On the application side, we have tested our techniques on puzzling Seljuk patterns (from Kayseri) to demonstrate how the developed techniques give way to computational creativity. Apart from the techniques we have developed, the most important contribution of our work is that shapes are treated as perceived wholes rather than composed, as compellingly demonstrated by Seljuk pattern experiments.

This thesis assumes the architectural design process as a systematic study, in which knowledge is stored, organized and operated on by computational methods. From this perspective, the study explores the efforts for systemizing the architectural design process. Firstly, the focus is on the early approaches of systemizing design in the Design Methods Movement. The thesis identifies and evaluates the use of a number of critical concepts in this movement and in recent architecture practice, in order to see the development and transformation of design methods in terms of computing knowledge in a systematic way. The thesis evaluates the features that make design systematic within the Design Methods Movement and inquires whether such features like complexity, hierarchy, feedback loops and selection are influential in recent computational design methods of architecture. The thesis looks into two generative design methods, namely evolutionary design and shape grammars, which have been studied by designers since the 1960s, the start of the Design Methods Movement. These two methods exemplify current systematic approaches to design and according to the thesis these are the instances of how recent architecture employs the features discussed as characteristic in the Design Methods Movement.

The objective of this thesis is to develop a method for the reconfiguration of three-dimensional modular robots. A modular robot is composed of simple individual building blocks or modules. Each of these modules needs to be controlled and actuated individually in order to make the robot perform useful tasks. The presented method allows us to reconfigure arbitrary initial configurations of modules into any pre-specified target configuration by using graph grammar rules that rely on local information only. Local in a sense that each module needs just information from neighboring modules in order to decide its next reconfiguration step. The advantage of this approach is that the modules do not need global knowledge about the whole configuration. We propose a two stage reconfiguration process composed of a centralized planning stage and a decentralized, rule-based reconfiguration stage. In the first stage, paths are planned for each module and then rewritten into a ruleset, also called a graph grammar. Global knowledge about the configuration is available to the planner. In stage two, these rules are applied in a decentralized fashion by each node individually and with local knowledge only. Each module can check the ruleset for applicable rules in parallel. This approach has been implemented in Matlab and currently, we are able to generate rulesets for arbitrary homogeneous input configurations.

In the information age of today, vast amounts of sensitive and confidential data is exchanged over an array of different mediums. Accompanied with this phenomenon is a comparable increase in the number and types of attacks to acquire this information. Information security and data consistency have hence, become quintessentially important. Log file analysis has proven to be a good defense mechanism as logs provide an accessible record of network activities in the form of server generated messages. However, manual analysis is tedious and prohibitively time consuming. Traditional log analysis techniques, based on pattern matching and data mining approaches, are ad hoc and cannot readily adapt to different kinds of log files. The goal of this research is to explore the use of grammar inference for log file analysis in order to build a more adaptive, flexible and generic method for message categorization, anomaly detection and reporting. The grammar inference process employs robust parsing, islands grammars and source transformation techniques. We test the system by using three different kinds of log file training sets as input and infer a grammar and generate message categories for each set. We detect anomalous messages in new log files using the inferred grammar as a catalog of valid traces and present a reporting program to extract the instances of specified message categories from the log files. / Thesis (Master, Computing) -- Queen's University, 2008-05-22 14:12:30.199

No description available.

A domain-specific embedded language (DSEL) is a domain-specific programming language with no concrete syntax of its own. Defined as a set of combinators encapsulated in a module, it borrows the syntax and tools (such as type-checkers and compilers) of its host language; hence it is economical to design, introduce, and maintain. Unfortunately, this economy is counterbalanced by a lack of room for growth. DSELs cannot match sophisticated domain-specific languages that offer tools for domainspecific error-checking and optimisation. These tools are usually based on syntactic analyses, so they do not work on DSELs. Abstract interpretation is a technique ideally suited to the analysis of DSELs, due to its semantic, rather than syntactic, approach. It is based upon the observation that analysing a program is equivalent to evaluating it over an abstract semantic domain. The mathematical properties of the abstract domain are such that evaluation reduces to solving a mutually recursive set of equations. This dissertation shows how abstract interpretation can be applied to a DSEL by replacing it with an abstract implementation of the same interface; evaluating a program with the abstract implementation yields an analysis result, rather than an executable. The abstract interpretation of DSELs provides a foundation upon which to build sophisticated error-checking and optimisation tools. This is illustrated with three examples: an alphabet analyser for CSP, an ambiguity test for parser combinators, and a definedness test for attribute grammars. Of these, the ambiguity test for parser combinators is probably the most important example, due to the prominence of parser combinators and their rather conspicuous lack of support for the well-known LL(k) test. In this dissertation, DSELs and their signatures are encoded using the polymorphic lambda calculus. This allows the correctness of the abstract interpretation of DSELs to be proved using the parametricity theorem: safety is derived for free from the polymorphic type of a program. Crucially, parametricity also solves a problem commonly encountered by other analysis methods: it ensures the correctness of the approach in the presence of higher-order functions.

Made available in DSpace on 2014-12-17T15:48:09Z (GMT). No. of bitstreams: 1 VivianeMR_DISSERT.pdf: 1295596 bytes, checksum: 1bb5688145cd1ce7005121d9de48c246 (MD5) Previous issue date: 2013-12-13 / The work proposed by Cleverton Hentz (2010) presented an approach to define tests from the formal description of a program s input. Since some programs, such as compilers, may have their inputs formalized through grammars, it is common to use context-free grammars to specify the set of its valid entries. In the original work the author developed a tool that automatically generates tests for compilers. In the present work we identify types of problems in various areas where grammars are used to describe them , for example, to specify software configurations, which are potential situations to use LGen. In addition, we conducted case studies with grammars of different domains and from these studies it was possible to evaluate the behavior and performance of LGen during the generation of sentences, evaluating aspects such as execution time, number of generated sentences and satisfaction of coverage criteria available in LGen / O trabalho proposto por Cleverton Hentz (2010) apresentou uma abordagem para defini??o de testes a partir da descri??o formal das entradas do programa. Considerando que alguns programas podem ter suas entradas formalizadas atrav?s de gram?ticas, como ? o caso dos compiladores, ? comum o uso de gram?ticas livres de contexto para especificar o conjunto de entradas v?lidas. No trabalho original foi desenvolvida LGen, uma ferramenta que consiste na gera??o autom?tica de testes para compiladores. No presente trabalho identificamos tipos de problemas recorrentes em diferentes ?reas, onde gram?ticas s?o usadas para descrev?-los, como por exemplo, para especificar configura??es de software, e que s?o situa??es potenciais para o uso de LGen. Al?m disso, realizamos estudos de caso com gram?ticas de dom?nios diferentes e a partir destes estudos foi poss?vel avaliar o comportamento e o desempenho de LGen durante o processo de gera??o das senten?as, avaliando aspectos como tempo de execu??o, quantidade de senten?as geradas e satisfa??o de crit?rios de cobertura dispon?veis em LGen

Vários métodos de especificação procuram realizar a modelagem de sistemas sob três visões: uma visão funcional, que procura apresentar as informações que trafegam entre os diversos componentes do sistema, uma visão de dados, que apresenta as relações entre as estruturas de dados estáticas do sistema e a visão dinâmica, que mostra as transformações que o sistema pode sofrer ao longo do tempo. Alguns modelos procuram integrar mais de uma visão, mas, em geral, os modelos possuem sérias deficiências ao tentarem representar mais de um aspecto do sistema ao mesmo tempo, sendo necessário o apoio de outros métodos. Este trabalho apresenta um método de especificação de sistemas que procura integrar a modelagem de dados com a modelagem funcional e dinâmica utilizando-se, para isso, das Gramáticas de Grafos como método formal de especificação. Sendo um grafo formado por vértices, arestas e rótulos, pode-se facilmente criar uma camada de abstração em que o usuário (em geral responsável pela análise de sistemas) manipule um método de especificação com o qual já convive, agora com uma semântica formal definida. Espera-se, com a aplicação do método, gerar modelos passíveis de prova, não ambíguos e que promovam um incremento de qualidade no sistema gerado. / Several specification methods try to realize system modeling following three visions: the functional vision, which is based on representing the information exchange among the several components of the system; the data vision, which represents the relations among the static data structures of the system; and the dynamic vision, which presents the transformations the system may endure over the time. Some models exist that try to integrate more than one of these visions, but, in general, they suffer from deficiencies when trying to represent more than one aspect of the system at the same time, in which case the use of other methods is necessary. This work presents a novel method of systems specification that attempts to integrate data modeling with functional and dynamic modelings using, for this, Graph Grammars as its formal specification method. A graph, being made of nodes, edges and labels, is appropriate for creating, easily, an abstraction layer in which the user (usually responsible for the system analysis) manipulates a specification method which is known to him, but now with a well defined formal semantics. We hope, by applying this method, to generate provable, unambiguous models which promote an increase in the quality of the generated system.

La construction de ressources linguistiques arabes riches en informations syntaxiques constitue un enjeu important pour le développement de nouveaux outils de traitement automatique. Cette thèse propose une approche pour la création d’un treebank de l’arabe intégrant des informations d’un type nouveau reposant sur le formalisme des Grammaires de Propriétés. Une propriété syntaxique caractérise une relation pouvant exister entre deux unités d’une certaine structure syntaxique. Cette grammaire est induite automatiquement à partir du treebank arabe ATB, ce qui constitue un enrichissement de cette ressource tout en conservant ses qualités. Cet enrichissement a été également appliqué aux résultats d’analyse d’un analyseur état de l’art du domaine, le Stanford Parser, offrant la possibilité d’une évaluation s’appuyant sur un ensemble de mesures obtenues à partir de cette ressource. Les étiquettes des unités de cette grammaire sont structurées selon une hiérarchie de types permettant la variation de leur degré de granularité, et par conséquent du degré de précision des informations. Nous avons pu ainsi construire, à l’aide de cette grammaire, d’autres ressources linguistiques arabes. En effet, sur la base de cette nouvelle ressource, nous avons développé un analyseur syntaxique probabiliste à base de propriétés syntaxiques, le premier appliqué pour l'arabe. Une grammaire de propriétés lexicalisée probabiliste fait partie de son modèle d’apprentissage pour pouvoir affecter positivement le résultat d’analyse et caractériser ses structures syntaxiques avec les propriétés de ce modèle. Nous avons enfin évalué les résultats obtenus en les comparant à celles du Stanford Parser. / The building of syntactically informative Arabic linguistic resources is a major issue for the development of new machine processing tools. We propose in this thesis to create an Arabic treebank that integrates a new type of information, which is based on the Property Grammar formalism. A syntactic property is a relation between two units of a given syntactic structure. This grammar is automatically induced from the Arabic treebank ATB. We enriched this resource with the property representations of this grammar, while retaining its qualities. We also applied this enrichment to the parsing results of a state-of-the-art analyzer, the Stanford Parser. This provides the possibility of an evaluation using a measure set, which is calculated on this resource. We structured the tags of the units in this grammar according to a type hierarchy. This permit to vary the granularity level of these units, and consequently the accuracy level of the information. We have thus been able to construct, using this grammar, other Arabic linguistic resources. Secondly, based on this new resource, we developed a probabilistic syntactic parser based on syntactic properties. This is the first analyzer of this type that we have applied to Arabic. In the learning model, we integrated a probabilistic lexicalized property grammar that may positively affect the parsing result and describe its syntactic structures with its properties. Finally, we evaluated the parsing results of this approach by comparing them to those of the Stanford Parser.

Vários métodos de especificação procuram realizar a modelagem de sistemas sob três visões: uma visão funcional, que procura apresentar as informações que trafegam entre os diversos componentes do sistema, uma visão de dados, que apresenta as relações entre as estruturas de dados estáticas do sistema e a visão dinâmica, que mostra as transformações que o sistema pode sofrer ao longo do tempo. Alguns modelos procuram integrar mais de uma visão, mas, em geral, os modelos possuem sérias deficiências ao tentarem representar mais de um aspecto do sistema ao mesmo tempo, sendo necessário o apoio de outros métodos. Este trabalho apresenta um método de especificação de sistemas que procura integrar a modelagem de dados com a modelagem funcional e dinâmica utilizando-se, para isso, das Gramáticas de Grafos como método formal de especificação. Sendo um grafo formado por vértices, arestas e rótulos, pode-se facilmente criar uma camada de abstração em que o usuário (em geral responsável pela análise de sistemas) manipule um método de especificação com o qual já convive, agora com uma semântica formal definida. Espera-se, com a aplicação do método, gerar modelos passíveis de prova, não ambíguos e que promovam um incremento de qualidade no sistema gerado. / Several specification methods try to realize system modeling following three visions: the functional vision, which is based on representing the information exchange among the several components of the system; the data vision, which represents the relations among the static data structures of the system; and the dynamic vision, which presents the transformations the system may endure over the time. Some models exist that try to integrate more than one of these visions, but, in general, they suffer from deficiencies when trying to represent more than one aspect of the system at the same time, in which case the use of other methods is necessary. This work presents a novel method of systems specification that attempts to integrate data modeling with functional and dynamic modelings using, for this, Graph Grammars as its formal specification method. A graph, being made of nodes, edges and labels, is appropriate for creating, easily, an abstraction layer in which the user (usually responsible for the system analysis) manipulates a specification method which is known to him, but now with a well defined formal semantics. We hope, by applying this method, to generate provable, unambiguous models which promote an increase in the quality of the generated system.