• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 61
  • 50
  • 13
  • 11
  • 10
  • 1
  • 1
  • 1
  • 1
  • Tagged with
  • 158
  • 40
  • 29
  • 28
  • 25
  • 23
  • 22
  • 21
  • 20
  • 18
  • 18
  • 18
  • 18
  • 17
  • 16
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
41

Specification, implementation and verification of refactorings

Schaefer, Max January 2010 (has links)
Refactoring is the process of reorganising or restructuring code by means of behaviour-preserving program transformations, themselves called refactorings. Most modern development environments come with built-in support for refactoring in the form of automated refactorings that the user can perform at the push of a button. Implementing refactorings is notoriously complex, however, and even state-of-the-art implementations have very low standards of correctness and can introduce subtle changes of behaviour into refactored programs. In this thesis, we develop concepts and techniques that make it possible to give concise, modular specifications of refactorings. These specifications are precise enough to cover all details of the object language, and thus give rise to full featured, high-quality refactoring implementations. Their modularity, on the other hand, makes them amenable to formal proof, and hence opens the door to the rigorous verification of refactorings. We discuss a disciplined approach to maintaining name bindings and avoiding name capture by treating the binding from a name to the declaration it refers to as a dependency that the refactoring has to preserve. This approach readily generalises to other types of dependencies for capturing control flow, data flow and synchronisation behaviour. To implement complex refactorings, it is often helpful for the refactoring to internally work on a richer language with language extensions that make the transformation easier to express. We show how this allows the decomposition of refactorings into small microrefactorings that can be specified, implemented and verified in isolation. We evaluate our approach by giving specifications and implementations of many commonly used refactorings that are concise, yet match the implementations in the popular Java development environment Eclipse in terms of features, and outperform them in terms of correctness. We give detailed informal correctness proofs for some of our specifications, which are greatly aided by their modular structure. Finally, we discuss a rigorous formalisation of the central name binding framework used by most of our specifications in the theorem prover Coq, and show how its correctness can be established mechanically.
42

Rich Linguistic Structure from Large-Scale Web Data

Yamangil, Elif 18 October 2013 (has links)
The past two decades have shown an unexpected effectiveness of Web-scale data in natural language processing. Even the simplest models, when paired with unprecedented amounts of unstructured and unlabeled Web data, have been shown to outperform sophisticated ones. It has been argued that the effectiveness of Web-scale data has undermined the necessity of sophisticated modeling or laborious data set curation. In this thesis, we argue for and illustrate an alternative view, that Web-scale data not only serves to improve the performance of simple models, but also can allow the use of qualitatively more sophisticated models that would not be deployable otherwise, leading to even further performance gains. / Engineering and Applied Sciences
43

Dependency based CCG derivation and application

Brewster, Joshua Blake 21 February 2011 (has links)
This paper presents and evaluates an algorithm to translate a dependency treebank into a Combinatory Categorial Grammar (CCG) lexicon. The dependency relations between a head and a child in a dependency tree are exploited to determine how CCG categories should be derived by making a functional distinction between adjunct and argument relations. Derivations for an English (CoNLL08 shared task treebank) and for an Italian (Turin University Treebank) dependency treebank are performed, each requiring a number of preprocessing steps. In order to determine the adequacy of the lexicons, dubbed DepEngCCG and DepItCCG, they are compared via two methods to preexisting CCG lexicons derived from similar or equivalent sources (CCGbank and TutCCG). First, a number of metrics are used to compare the state of the lexicon, including category complexity and category growth. Second, to measures the potential applicability of the lexicons in NLP tasks, the derived English CCG lexicon and CCGbank are compared in a sentiment analysis task. While the numeric measurements show promising results for the quality of the lexicons, the sentiment analysis task fails to generate a usable comparison. / text
44

Automated recognition of handwritten mathematics

MacLean, Scott January 2014 (has links)
Most software programs that deal with mathematical objects require input expressions to be linearized using somewhat awkward and unfamiliar string-based syntax. It is natural to desire a method for inputting mathematics using the same two-dimensional syntax employed with pen and paper, and the increasing prevalence of pen- and touch-based interfaces causes this topic to be of practical as well as theoretical interest. Accurately recognizing two-dimensional mathematical notation is a difficult problem that requires not only theoretical advancement over the traditional theories of string-based languages, but also careful consideration of runtime efficiency, data organization, and other practical concerns that arise during system construction. This thesis describes the math recognizer used in the MathBrush pen-math system. At a high level, the two-dimensional syntax of mathematical writing is formalized using a relational grammar. Rather than reporting a single recognition result, all recognizable interpretations of the input are simultaneously represented in a data structure called a parse forest. Individual interpretations may be extracted from the forest and reported one by one as the user requests them. These parsing techniques necessitate robust tree scoring functions, which themselves rely on several lower-level recognition processes for stroke grouping, symbol recognition, and spatial relation classification. The thesis covers the recognition, parsing, and scoring aspects of the MathBrush recognizer, as well as the algorithms and assumptions necessary to combine those systems and formalisms together into a useful and efficient software system. The effectiveness of the resulting system is measured through two accuracy evaluations. One evaluation uses a novel metric based on user effort, while the other replicates the evaluation process of an international accuracy competition. The evaluations show that not only is the performance of the MathBrush recognizer improving over time, but it is also significantly more accurate than other academic recognition systems.
45

Procedural reconstruction of buildings : towards large scale automatic 3D modeling of urban environments

Simon, Loïc 25 July 2011 (has links) (PDF)
This thesis is devoted to 2D and 3D modeling of urban environments using structured representations and grammars. Our approach introduces a semantic representation for buildings that encodes expected architectural constraints and is able to derive complex instances using fairly simple grammars. Furthermore, we propose two novel inference algorithms to parse images using such grammars. To this end, a steepest ascent hill climbing concept is considered to derive the grammar and the corresponding parameters from a single facade view. It combines the grammar constraints with the expected visual properties of the different architectural elements. Towards addressing more complex scenarios and incorporating 3D information, a second inference strategy based on evolutionary computational algorithms is adopted to optimize a two-component objective function introducing depth cues. The proposed framework was evaluated qualitatively and quantitatively on a benchmark of annotated facades, demonstrating robustness to challenging situations. Substantial improvement due to the strong grammatical context was shown in comparison to the performance of the same appearance models coupled with local priors. Therefore, our approach provides powerful techniques in response to increasing demand on large scale 3D modeling of real environments through compact, structured and semantic representations, while opening new perspectives for image understanding
46

Oprava nevalidních stromů vůči regulárním stromovým gramatikám / Correction of Invalid Trees with Respect to Regular Tree Grammars

Svoboda, Martin January 2015 (has links)
XML documents and related technologies represent one of the most widespread ways how data on the Web are maintained and interchanged. Unfortunately, many of the real-world documents contain various types of consistency issues that prevent their successful automated processing. In this thesis we focus on the problem of the structural invalidity and its correction. In particular, having one potentially invalid XML document modeled as a tree, and a schema in DTD or XML Schema languages modeled as a regular tree grammar, our goal is to find all the minimal corrections of this tree. The model we proposed builds on top of the recursively nested structures of correction multigraphs, where the shortest paths are being found. For this purpose we formally introduce three correction strategies with different pruning optimizations applied. According to the experiments we performed, the refinement correction strategy not only significantly outperforms all the other existing approaches, but also guarantees important characteristics the others cannot. Powered by TCPDF (www.tcpdf.org)
47

Leveraging MWEs in practical TAG parsing : towards the best of the two worlds / Optimisation d'analyse syntaxique basée sur les grammaires d'arbres adjoints grâce à la modélisation d'expression polylexicales et à l'algorithme A

Waszczuk, Jakub 26 June 2017 (has links)
Dans ce mémoire, nous nous penchons sur les expressions polylexicales (EP) et leurs relations avec l’analyse syntaxique, la tâche qui consiste à déterminer les relations syntaxiques entre les mots dans une phrase donnée. Le défi que posent les EP dans ce contexte, par rapport aux expressions linguistiques régulières, provient de leurs propriétés parfois inattendues qui les rendent difficiles à gérer dans te traitement automatique des langues. Dans nos travaux, nous montrons qu’il est pourtant possible de profiter de ce cette caractéristique des EP afin d’améliorer les résultats d’analyse syntaxique. Notamment, avec les grammaires d’arbres adjoints (TAGs), qui fournissent un cadre naturel et puissant pour la modélisation des EP, ainsi qu’avec des stratégies de recherche basées sur l’algorithme A* , il est possible d’obtenir des gains importants au niveau de la vitesse sans pour autant détériorer la qualité de l’analyse syntaxique. Cela contraste avec des méthodes purement statistiques qui, malgré l’efficacité, ne fournissent pas de solutions satisfaisantes en ce qui concerne les EP. Nous proposons un analyseur syntaxique novateur qui combine les grammaires TAG avec La technique A*, axé sur la prédiction des EP, dont les fonctionnalités permettent des applications à grande échelle, facilement extensible au contexte probabiliste. / In this thesis, we focus on multiword expressions (MWEs) and their relationships with syntactic parsing. The latter task consists in retrieving the syntactic relations holding between the words in a given sentence. The challenge of MWEs in this respect is that, in contrast to regular linguistic expressions, they exhibit various irregular properties which make them harder to deal with in natural language processing. In our work, we show that the challenge of the MWE-related irregularities can be turned into an advantage in practical symbolic parsing. Namely, with tree adjoining grammars (TAGs), which provide first-cLass support for MWEs, and A* search strategies, considerable speed-up gains can be achieved by promoting MWE-based analyses with virtually no loss in syntactic parsing accuracy. This is in contrast to purely statistical state-of-the-art parsers, which, despite efficiency, provide no satisfactory support for MWEs. We contribute a TAG-A* -MWE-aware parsing architecture with facilities (grammar compression and feature structures) enabling real-world applications, easily extensible to a probabilistic framework.
48

Object-oriented graph grammars

Ferreira, Ana Paula Ludtke January 2005 (has links)
Esta tese apresenta um modelo conceitual para modelagem e vericação de espe- cificações de sistemas orientados a objeto. Mais especificiamente, uma extensão da abordagem algébrica baseada em single-pushouts para gramáticas de grafos tipadas é desenvolvida, onde os morfismos de tipagem são compatíveis com as relações de ordem sobre os nodos e (hiper)arcos de um grafo, e que representam, respectivamente, as relações de herança entre classes e sobrescrita de métodos. O trabalho é dividido em trÊs linhas principais: especificações de sistemas, comportamento dinâmico de programas, e verificaçaõ formal de sistemas orientados a objeto. A hierarquia de classes de um sistema orientado a objetoé modelada por um hipergrafo rotulado chamado grafo de classes, cujos conjuntos de nodos e arcos possuem uma relação de ordem parcial restrita, com o objetivo de modelar herança e sobrescrita de métodos. Restrições adicionais garantem que grafos de classes provÊm um modelo fiel e adequado da maneira como as classes de um sistema orientado a objetos s~ao efetivamente organizadas e combinadas. Grafos orientados a objeto são hipergrafos tipados sobre um grafo de classes. O morfismo de tipagem exige que hiperarcos mapeados preservem as relações existentes entre os seus nodos de origem e destino. Esta característica modela a heran»ca de forma adequada, visto que qualquer objeto pode fazer uso de atributos ou mensagens herdadas. Mor¯smos entre grafos orientados a objeto asseguram que o polimorfismo de subclasses seja uma característica intrínseca do formalismo aqui apresentado. Regras orientadas a objeto respeitam os princípios de encapsulamento e oclusão da informação do paradigma. Uma derivação direta (ou aplicação de regra)é uma soma amalgamada (pushout) na categoria de grafos orientados a objeto e seus morfismos. Gramáticas de grafos orientados a objeto modelam o comportamento dinâmico de sistemas. Uma semântica observacional para gramáticas de grafos orientados a objeto, baseada em sistemas de transição rotulados, é definida. Tal semântica é baseada na noção de entidades visíveis (objetos ou mensagens), e que representam os elementos importantes no processo de verificação de propriedades do sistema especificado pela gramática. Finalmente, uma tradução formal de gramáticas de grafos orientados a objeto para programas na linguagem Promela é definida. Objetos são traduzidos como pro- cessos em Promela, e a troca de mensagens entre objetos é implementada com canais de comunicação. Herança, polimorfismo e ligação dinÂmica são implementados no programa Promela, que originalmente não suporta nenhuma dessas caraterísticas. A verificação de propriedades do programa pode ser efetuada tanto sobre estados como sobre eventos. / This thesis presents a graph-based formal framework to model and verify object- oriented specifications. More specifically, an extension of the algebraic single- pushout approach to (typed) graph grammars is developed, where the typing mor- phisms are compatible with the order relations defined over nodes and edges to represent, respectively, inheritance and overriding of classes and methods. This work is divided in three main lines: static specifications, dynamic behaviour, and formal verification of object-oriented systems. The object-oriented class hierarchy structure is modeled by a graph structure called class-model graph, whose set of nodes and edges have a restricted partial order relation over them, to model inheritance and method overriding. The underlying relations of such sets obey additional restrictions, intended to assure that class- model graphs provide an adequate and faithful model of how object-oriented classes are organized and combined. Object-oriented graph grammars model the dynamics of object-oriented systems. Object-oriented graphs are hypergraphs typed over a class-model graph, but the typing morphism is more flexible than the traditional one, in the sense that mapped hyperedges need to preserve relations between sources and targets. This feature adequately models inheritance, for any object can make use of inherited attributes or messages. Morphisms between object-oriented graphs assure that subclass poly- morphism is a built-in feature of the formalism. Object-oriented rules respect the principles of encapsulation and information hiding of the object-oriented paradigm. A direct derivation (or rule application) is shown to be a pushout in the category of object-oriented graphs and their morphisms. An observational semantics for object-oriented graph grammars, based on a labeled transition system, is presented. This semantics is based on a notion of visible entities (objects or messages), which are the elements we are interested in for verification purposes. Finally, a formal translation from object-oriented graph grammars specifications into Promela programs is defined. Objects in the system graph are translated as Promela processes, and message exchange is implemented with buffered communication channels. The semantics of grammar rule application is preserved by the nondeterminism in the choice of which message to consume. Inheritance, polymorphism and dynamic binding are implemented in the Promela program, which originally does not support it. The translation presented assures that both state and event verification can be performed.
49

Modelagem e simulação de algoritmos paralelos baseados em operações com DNA / DNA-Based modelling and simulation of parallel algorithms

Cervo, Leonardo Vieira January 2002 (has links)
A área de biologia computacional está vivendo um crescimento rápido causado pela revolução no estudo de genômas e pelo avanço das técnicas de manipulação do material genético. Com essas novas tecnologias para manipulação de seqüências, a importância de achar uma solução eficiente para os problemas chamados de intratáveis também cresceu, pois muitos problemas envolvidos na análise de DNA pertencem a essa classe de problemas. Uma abordagem para achar essas soluções é usar o próprio DNA para realizar computação, aproveitando o paralelismo massivo utilizado em operações que manipulam seqüências de DNA. Isto é estudado na área de computação com DNA. Esse trabalho propõe um modelo formal para representar a estrutura da molécula de DNA e das operações que são realizadas com ela em laboratório. Este modelo ajuda a preencher a necessidade de uma descrição matemática que possa ser usada para analisar algoritmos baseados em DNA, assim como possibilitar a simulaç~o desses algoritmos em um computador. Foi utilizada a teoria de gramáticas de grafos, uma linguagem de especificação formal, para modelar as seqüências de DNA e suas I operações. O trabalho apresenta um estudo da estrutura da molécula de DNA, deScrevendo suas características e as principais operações que são realizadas para sua manipulação em laboratório. Uma descrição da teoria de Gramática de Grafos e sua aplicação também é apresentada. Para validação do modelo proposto as especificações resultantes foram adaptadas para o formato L-systems, outra linguagem de especificação formal, permitindo realizar a simulação da especificação no ambiente L-Studio. / The area of computational biology is living a fast growth, fed with a revolution in the study of genomes and with the advance in the techniques of genetic material manipulation. With these new technologies for manipulation of sequences, the relevance of finding efficient solution to the so-called computer intractable problems has also grown, because many problems involved in analyzing DNA belong to this class of problems. One approach to find such solutions is to use DNA itself to perform computations, taking advantage of the massive parallelism involved in operations that manipulate DNA sequences. This is what is studied in the area ofDNA computing. This work proposes a formal model to represent the DNA structure and the operations performed in laboratory with it. This model helps to fill the need of a mathematical description that can be used to analyze DNA-based algorithms, as well as for simulating such algorithms in a computer. We use graph grammars, a formal specification language, to model the DNA sequences and operations. The work presents a study of the DNA molecule structure, describing its features and the main operations performed for manipulation in laboratory. A description of the theory of Graph Grammars and its application are presented too. To validate the proposed model, the resulting DNA-graph grammar specifications are then translated into the L-systems format, another formal specification language, allowing for the simulation of the specifications using the L-Studio environment.
50

Extração e representação semântica de fatos temporais / EXTIO – extraction of temporal information using ontologies

Gallina, Leandro Zulian January 2012 (has links)
Este trabalho descreve EXTIO (Extraction of Temporal Information Using Ontologies), uma abordagem que permite a normalização de expressões temporais e a organização em ontologia de fatos temporais extraídos de texto em linguagem natural. Isto permite que motores de busca possam aproveitar melhor a informação temporal de páginas daWeb, realizando inferências sobre fatos temporais. EXTIO propõe: a normalização de expressões temporais relativas através de uma gramática formal para a língua inglesa; e a organização de fatos temporais extraídos do texto normalizado em uma ontologia. Expressões temporais relativas são construções textuais de tempo que se referem a uma data absoluta cujo valor é relativo a outra data. Por exemplo, a expressão “three months ago” (três meses atrás) é uma expressão temporal relativa, pois seu surgimento no texto se refere a uma data três meses antes da data de publicação do documento. Experimentos demonstram que a gramática formal proposta para a normalização de expressões temporais relativas supera o baseline na eficácia da normalização e no tempo de processamento de documentos em linguagem natural. A principal contribuição deste trabalho é a gramática formal para normalização de expressões temporais relativas de texto na língua inglesa. Também é contribuição deste trabalho o processamento semântico da informação temporal disponível em formato texto em documentos, para que possa ser melhor aproveitada por motores de busca. / This work describes EXTIO, an approach for the normalization of temporal expressions and the semantic organization of temporal facts extracted from natural language text. This approach allows search engines to benefit from temporal information in Web pages, performing inferences on temporal facts. EXTIO proposes: the normalization of relative temporal expressions through a formal grammar for the English language; and the organization of temporal facts extracted from normalized text in an ontology. Relative temporal expressions are textual time structures that refer to an absolute date whose value is relative to another date. For instance, “three months ago” is a relative temporal expression because its appearance in the text refers to a date three months before the document publication date. Experiments show that the proposed formal grammar for the normalization of relative temporal expressions has a better performance than the baseline in effectiveness and processing time. The main contribution of this work is the formal grammar for the normalization of temporal expressions in natural language text in English. Another contribution of this work is the semantic processing of temporal information available in documents, so that search engines may benefit from this information.

Page generated in 0.0823 seconds