Dissertations / Theses on the topic 'Structural Graph Representations'

El reconeixement de patrons és la tasca que pretén distingir objectes entre diferents classes. Quan aquesta tasca es vol solucionar de forma automàtica un pas crucial és el com representar formalment els patrons a l'ordinador. En funció d'aquests formalismes, podem distingir entre el reconeixement estadístic i l'estructural. El primer descriu objectes com un conjunt de mesures col·locats en forma del que s'anomena un vector de característiques. El segon assumeix que hi ha relacions entre parts dels objectes que han de quedar explícitament representades i per tant fa servir estructures relacionals com els grafs per codificar la seva informació inherent. Els espais vectorials són una estructura matemàtica molt flexible que ha permès definir diverses maneres eficients d'analitzar patrons sota la forma de vectors de característiques. De totes maneres, la representació vectorial no és capaç d'expressar explícitament relacions binàries entre parts dels objectes i està restrigida a mesurar sempre, independentment de la complexitat dels patrons, el mateix nombre de característiques per cadascun d'ells. Les representacions en forma de graf presenten la situació contrària. Poden adaptar-se fàcilment a la complexitat inherent dels patrons però introdueixen un problema d'alta complexitat computational, dificultant el disseny d'eines eficients per al procés i l'anàlisis de patrons. Resoldre aquesta paradoxa és el principal objectiu d'aquesta tesi. La situació ideal per resoldre problemes de reconeixement de patrons seria el representar-los fent servir estructures relacionals com els grafs, i a l'hora, poder fer ús del ric repositori d'eines pel processament de dades del reconeixement estadístic. Una solució elegant a aquest problema és la de transformar el domini dels grafs en el domini dels vectors, on podem aplicar qualsevol algorisme de processament de dades. En altres paraules, assignant a cada graf un punt en un espai vectorial, automàticament tenim accés al conjunt d'algorismes del món estadístic per aplicar-los al domini dels grafs. Aquesta metodologia s'anomena graph embedding. En aquesta tesi proposem de fer una associació de grafs a vectors de característiques de forma simple i eficient fixant l'atenció en la informació d'etiquetatge dels grafs. En particular, comptem les freqüències de les etiquetes dels nodes així com de les aretes entre etiquetes determinades. Tot i la seva localitat, aquestes característiques donen una representació prou robusta de les propietats globals dels grafs. Primer tractem el cas de grafs amb etiquetes discretes, on les característiques són sencilles de calcular. El cas continu és abordat com una generalització del cas discret, on enlloc de comptar freqüències d'etiquetes, ho fem de representants d'aquestes. Ens trobem que les representacions vectorials que proposem pateixen d'alta dimensionalitat i correlació entre components, i tractem aquests problems mitjançant algorismes de selecció de característiques. També estudiem com la diversitat de diferents representacions pot ser explotada per tal de millorar el rendiment de classificadors base en el marc d'un sistema de múltiples classificadors. Finalment, amb una extensa evaluació experimental mostrem com la metodologia proposada pot ser calculada de forma eficient i com aquesta pot competir amb altres metodologies per a la comparació de grafs.
Pattern recognition is the task that aims at distinguishing objects among different classes. When such a task wants to be solved in an automatic way a crucial step is how to formally represent such patterns to the computer. Based on the different representational formalisms, we may distinguish between statistical and structural pattern recognition. The former describes objects as a set of measurements arranged in the form of what is called a feature vector. The latter assumes that relations between parts of the underlying objects need to be explicitly represented and thus it uses relational structures such as graphs for encoding their inherent information. Vector spaces are a very flexible mathematical structure that has allowed to come up with several efficient ways for the analysis of patterns under the form of feature vectors. Nevertheless, such a representation cannot explicitly cope with binary relations between parts of the objects and it is restricted to measure the exact same number of features for each pattern under study regardless of their complexity. Graph-based representations present the contrary situation. They can easily adapt to the inherent complexity of the patterns but introduce a problem of high computational complexity, hindering the design of efficient tools to process and analyze patterns. Solving this paradox is the main goal of this thesis. The ideal situation for solving pattern recognition problems would be to represent the patterns using relational structures such as graphs, and to be able to use the wealthy repository of data processing tools from the statistical pattern recognition domain. An elegant solution to this problem is to transform the graph domain into a vector domain where any processing algorithm can be applied. In other words, by mapping each graph to a point in a vector space we automatically get access to the rich set of algorithms from the statistical domain to be applied in the graph domain. Such methodology is called graph embedding. In this thesis we propose to associate feature vectors to graphs in a simple and very efficient way by just putting attention on the labelling information that graphs store. In particular, we count frequencies of node labels and of edges between labels. Although their locality, these features are able to robustly represent structurally global properties of graphs, when considered together in the form of a vector. We initially deal with the case of discrete attributed graphs, where features are easy to compute. The continuous case is tackled as a natural generalization of the discrete one, where rather than counting node and edge labelling instances, we count statistics of some representatives of them. We encounter how the proposed vectorial representations of graphs suffer from high dimensionality and correlation among components and we face these problems by feature selection algorithms. We also explore how the diversity of different embedding representations can be exploited in order to boost the performance of base classifiers in a multiple classifier systems framework. An extensive experimental evaluation finally shows how the methodology we propose can be efficiently computed and compete with other graph matching and embedding methodologies.

In this thesis we describe subclasses of a class of graphs with three types of edges, called loopless mixed graphs (LMGs). The class of LMGs contains almost all known classes of graphs used in the literature of graphical Markov models. We focus in particular on the subclass of ribbonless graphs (RGs), which as special cases include undirected graphs, bidirected graphs, and directed acyclic graphs, as well as ancestral graphs and summary graphs. We define a unifying interpretation of independence structure for LMGs and pairwise and global Markov properties for RGs, discuss their maximality, and, in particular, prove the equivalence of pairwise and global Markov properties for graphoids defined over the nodes of RGs. Three subclasses of LMGs (MC, summary, and ancestral graphs) capture the modified independence model after marginalisation over unobserved variables and conditioning on selection variables of variables satisfying independence restrictions represented by a directed acyclic graph (DAG). We derive algorithms to generate these graphs from a given DAG or from a graph of a specific subclass, and we study the relationships between these classes of graphs. Finally, a manual and codes are provided that explain methods and functions in R for implementing and generating various graphs studied in this thesis.

Many digital models used in entertainment, medical visualization, material science, architecture, Geographic Information Systems (GIS), and mechanical Computer Aided Design (CAD) are defined in terms of their boundaries. These boundaries are often approximated using triangle meshes. The complexity of models, which can be measured by triangle count, increases rapidly with the precision of scanning technologies and with the need for higher resolution. An increase in mesh complexity results in an increase of storage requirement, which in turn increases the frequency of disk access or cache misses during mesh processing, and hence decreases performance. For example, in a test application involving a mesh with 55 million triangles in a machine with 4GB of memory versus a machine with 1GB of memory, performance decreases by a factor of about 6000 because of memory thrashing. To help reduce memory thrashing, we focus on decreasing the average storage requirement per triangle measured in 32-bit integer references per triangle (rpt). This thesis covers compact connectivity representation for triangle meshes and discusses four data structures: 1. Sorted Opposite Table (SOT), which uses 3 rpt and has been extended to support tetrahedral meshes. 2. Sorted Quad (SQuad), which uses about 2 rpt and has been extended to support streaming. 3. Laced Ring (LR), which uses about 1 rpt and offers an excellent compromise between storage compactness and performance of mesh traversal operators. 4. Zipper, an extension of LR, which uses about 6 bits per triangle (equivalently 0.19 rpt), therefore is the most compact representation. The triangle mesh data structures proposed in this thesis support the standard set of mesh connectivity operators introduced by the previously proposed Corner Table at an amortized constant time complexity. They can be constructed in linear time and space from the Corner Table or any equivalent representation. If geometry is stored as 16-bit coordinates, using Zipper instead of the Corner Table increases the size of the mesh that can be stored in core memory by a factor of about 8.

In recent years, deep learning has made a significant impact in various fields – helping to push the state-of-the-art forward in many application domains. Convolutional Neural Networks (CNN) have been applied successfully to tasks such as visual object detection, image super-resolution, and video action recognition while Long Short-term Memory (LSTM) and Transformer networks have been used to solve a variety of challenging tasks in natural language processing. However, these popular deep learning architectures (i.e., CNNs, LSTMs, and Transformers) can only handle data that can be represented as grids or sequences. Due to this limitation, many existing deep learning approaches do not generalize to problem domains where the data is represented as graphs – social networks in social network analysis or molecular graphs in chemoinformatics, for instance. The goal of this thesis is to help bridge the gap by studying deep learning solutions that can handle graph data naturally. In particular, we explore deep learning-based approaches in the following areas. 1. Graph Attention. In the real-world, graphs can be both large – with many complex patterns – and noisy which can pose a problem for effective graph mining. An effective way to deal with this issue is to use an attention-based deep learning model. An attention mechanism allows the model to focus on task-relevant parts of the graph which helps the model make better decisions. We introduce a model for graph classification which uses an attention-guided walk to bias exploration towards more task-relevant parts of the graph. For the task of node classification, we study a different model – one with an attention mechanism which allows each node to select the most task-relevant neighborhood to integrate information from. 2. Graph Representation Learning. Graph representation learning seeks to learn a mapping that embeds nodes, and even entire graphs, as points in a low-dimensional continuous space. The function is optimized such that the geometric distance between objects in the embedding space reflect some sort of similarity based on the structure of the original graph(s). We study the problem of learning time-respecting embeddings for nodes in a dynamic network. 3. Brain Network Discovery. One of the fundamental tasks in functional brain analysis is the task of brain network discovery. The brain is a complex structure which is made up of various brain regions, many of which interact with each other. The objective of brain network discovery is two-fold. First, we wish to partition voxels – from a functional Magnetic Resonance Imaging scan – into functionally and spatially cohesive regions (i.e., nodes). Second, we want to identify the relationships (i.e., edges) between the discovered regions. We introduce a deep learning model which learns to construct a group-cohesive partition of voxels from the scans of multiple individuals in the same group. We then introduce a second model which can recover a hierarchical set of brain regions, allowing us to examine the functional organization of the brain at different levels of granularity. Finally, we propose a model for the problem of unified and group-contrasting edge discovery which aims to discover discriminative brain networks that can help us to better distinguish between samples from different classes.

Medical images have been used to depict the anatomy or function. Their high-dimensionality and their non-linearity nature makes their analysis a challenging problem. In this thesis, we address the medical image analysis from the viewpoint of statistical learning theory. First, we examine regularization methods for analyzing MRI data. In this direction, we introduce a novel regularization method, the k-support regularized Support Vector Machine. This algorithm extends the 1 regularized SVM to a mixed norm of both '1 and '2 norms. We evaluate our algorithm in a neuromuscular disease classification task. Second, we approach the problem of graph representation and comparison for analyzing medical images. Graphs are a technique to represent data with inherited structure. Despite the significant progress in graph kernels, existing graph kernels focus on either unlabeled or discretely labeled graphs, while efficient and expressive representation and comparison of graphs with continuous high-dimensional vector labels, remains an open research problem. We introduce a novel method, the pyramid quantized Weisfeiler-Lehman graph representation to tackle the graph comparison problem for continuous vector labeled graphs. Our algorithm considers statistics of subtree patterns based on the Weisfeiler-Lehman algorithm and uses a pyramid quantization strategy to determine a logarithmic number of discrete labelings. We evaluate our algorithm on two different tasks with real datasets. Overall, as graphs are fundamental mathematical objects and regularization methods are used to control ill-pose problems, both proposed algorithms are potentially applicable to a wide range of domains.

Representing and handling high-dimensional data has been increasingly ubiquitous in many real world-applications, such as computer vision, machine learning, and data mining. High-dimensional data usually have intrinsic low-dimensional structures, which are suitable for subsequent data processing. As a consequent, it has been a common demand to find low-dimensional data representations in many machine learning and data mining problems. Factorization methods have been impressive in recovering intrinsic low-dimensional structures of the data. When seeking low-dimensional representation of the data, traditional methods mainly face two challenges: 1) how to discover the most variational features/information from the data; 2) how to measure accurate nonlinear relationships of the data. As a solution to these challenges, traditional methods usually make use of a two-step approach by performing feature selection and manifold construction followed by further data processing, which omits the dependence between these learning tasks and produce inaccurate data representation. To resolve these problems, we propose to integrate feature learning and graph learning with factorization model, which allows the goals of learning features, constructing manifold, and seeking new data representation to mutually enhance and lead to powerful data representation capability. Moreover, it has been increasingly common that 2-dimensional (2D) data often have high dimensions of features, where each example of 2D data is a matrix with its elements being features. For such data, traditional data usually convert them to 1-dimensional vectorial data before data processing, which severely damages inherent structures of such data. We propose to directly use 2D data for seeking new representation, which enables the model to preserve inherent 2D structures of the data. We propose to seek projection directions to find the subspaces, in which spatial information is maximumly preserved. Also, manifold and new data representation are learned in these subspaces, such that the manifold are clean and the new representation is discriminative. Consequently, seeking projections, learning manifold and constructing new representation mutually enhance and lead to powerful data representation technique.

Thesis (Ph.D)--Electrical and Computer Engineering, Georgia Institute of Technology, 2010.
Committee Chair: Madisetti, Vijay; Committee Member: Jayant, Nikil; Committee Member: Lee, Chin-Hui; Committee Member: Ramachandran, Umakishore; Committee Member: Yalamanchili, Sudhakar. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Problemas de projeto de redes (PPRs) são muito importantes uma vez que envolvem uma série de aplicações em áreas da engenharia e ciências. Para solucionar as limitações de algoritmos convencionais para PPRs que envolvem redes complexas do mundo real (em geral modeladas por grafos completos ou mesmo esparsos de larga-escala), heurísticas, como os algoritmos evolutivos (EAs), têm sido investigadas. Trabalhos recentes têm mostrado que estruturas de dados adequadas podem melhorar significativamente o desempenho de EAs para PPRs. Uma dessas estruturas de dados é a representação nó-profundidade (NDE, do inglês Node-depth Encoding). Em geral, a aplicação de EAs com a NDE tem apresentado resultados relevantes para PPRs de larga-escala. Este trabalho investiga o desenvolvimento de uma nova representação, baseada na NDE, chamada representação nó-profundidade-grau (NDDE, do inglês Node-depth-degree Encoding). A NDDE é composta por melhorias nos operadores existentes da NDE e pelo desenvolvimento de novos operadores de reprodução possibilitando a recombinação de soluções. Nesse sentido, desenvolveu-se um operador de recombinação capaz de lidar com grafos não-completos e completos, chamado EHR (do inglês, Evolutionary History Recombination Operator). Foram também desenvolvidos operadores de recombinação que lidam somente com grafos completos, chamados de NOX e NPBX. Tais melhorias tem como objetivo manter relativamente baixa a complexidade computacional dos operadores para aumentar o desempenho de EAs para PPRs de larga-escala. A análise de propriedades de representações mostrou que a NDDE possui redundância, assim, foram propostos mecanismos para evitá-la. Essa análise mostrou também que o EHR possui baixa complexidade de tempo e não possui tendência, além de revelar que o NOX e o NPBX possuem uma tendência para árvores com topologia de estrela. A aplicação de EAs usando a NDDE para PPRs clássicos envolvendo grafos completos, tais como árvore geradora de comunicação ótima, árvore geradora mínima com restrição de grau e uma árvore máxima, mostrou que, quanto maior o tamanho das instâncias do PPR, melhor é o desempenho relativo da técnica em comparação com os resultados obtidos com outros EAs para PPRs da literatura. Além desses problemas, um EA utilizando a NDE com o operador EHR foi aplicado ao PPR do mundo real de reconfiguração de sistemas de distribuição de energia elétrica (envolvendo grafos esparsos). Os resultados mostram que o EHR possibilita reduzir significativamente o tempo de convergência do EA
Network design problems (NDPs) are very important since they involve several applications from areas of Engineering and Sciences. In order to solve the limitations of traditional algorithms for NDPs that involve real world complex networks (in general, modeled by large-scale complete or sparse graphs), heuristics, such as evolutionary algorithms (EAs), have been investigated. Recent researches have shown that appropriate data structures can improve EA performance when applied to NDPs. One of these data structures is the Node-depth Encoding (NDE). In general, the performance of EAs with NDE has presented relevant results for large-scale NDPs. This thesis investigates the development of a new representation, based on NDE, called Node-depth-degree Encoding (NDDE). The NDDE is composed for improvements of the NDE operators and the development of new reproduction operators that enable the recombination of solutions. In this way, we developed a recombination operator to work with both non-complete and complete graphs, called EHR (Evolutionary History Recombination Operator). We also developed two other operators to work only with complete graphs, named NOX and NPBX. These improvements have the advantage of retaining the computational complexity of the operators relatively low in order to improve the EA performance. The analysis of representation properties have shown that NDDE is a redundant representation and, for this reason, we proposed some strategies to avoid it. This analysis also showed that EHR has low running time and it does not have bias, moreover, it revealed that NOX and NPBX have bias to trees like stars. The application of an EA using the NDDE to classic NDPs, such as, optimal communication spanning tree, degree-constraint minimum spanning tree and one-max tree, showed that the larger the instance is, the better the performance will be in comparison whit other EAs applied to NDPs in the literatura. An EA using the NDE with EHR was applied to a real-world NDP of reconfiguration of energy distribution systems. The results showed that EHR significantly decrease the convergence time of the EA

Various data structures have been proposed for representing the connectivity of manifold triangle meshes. For example, the Extended Corner Table (ECT) stores V+6T references, where V and T respectively denote the vertex and triangle counts. ECT supports Random Access and Traversal (RAT) operators at Constant Amortized Time (CAT) cost. We propose two novel variations of ECT that also support RAT operations at CAT cost, but can be used to represent and process Simplicial 2-Complexes (S2Cs), which may represent star-connecting, non-orientable, and non-manifold triangulations along with dangling edges, which we call sticks. Vlist stores V+3T+3S+3(C+S-N) references, where S denotes the stick count, C denotes the number of edge-connected components and N denotes the number of star-connecting vertices. Ering stores 6T+3S+3(C+S-N) references, but has two advantages over Vlist: the Ering implementation of the operators is faster and is purely topological (i.e., it does not perform geometric queries). Vlist and Ering representations have two principal advantages over previously proposed representations for simplicial complexes: (1) Lower storage cost, at least for meshes with significantly more triangles than sticks, and (2) explicit support of side-respecting traversal operators which each walks from a corner on the face of a triangle t across an edge or a vertex of t, to a corner on a faces of a triangle or to an end of a stick that share a vertex with t, and this without ever piercing through the surface of a triangle.

The formalized and algorithmic study of human language within the field of Natural Language Processing (NLP) has motivated much theoretical work in the related field of formal languages, in particular the subfields of grammar and automata theory. Motivated and informed by NLP, the papers in this thesis explore the connections between expressibility – that is, the ability for a formal system to define complex sets of objects – and algorithmic complexity – that is, the varying amount of effort required to analyse and utilise such systems. Our research studies formal systems working not just on strings, but on more complex structures such as trees and graphs, in particular syntax trees and semantic graphs. The field of mildly context-sensitive languages concerns attempts to find a useful class of formal languages between the context-free and context-sensitive. We study formalisms defining two candidates for this class; tree-adjoining languages and the languages defined by linear context-free rewriting systems. For the former, we specifically investigate the tree languages, and define a subclass and tree automaton with linear parsing complexity. For the latter, we use the framework of parameterized complexity theory to investigate more deeply the related parsing problems, as well as the connections between various formalisms defining the class. The field of semantic modelling aims towards formally and accurately modelling not only the syntax of natural language statements, but also the meaning. In particular, recent work in semantic graphs motivates our study of graph grammars and graph parsing. To the best of our knowledge, the formalism presented in Paper III of this thesis is the first graph grammar where the uniform parsing problem has polynomial parsing complexity, even for input graphs of unbounded node degree.

Le but de notre travail est de définir un modèle de recherche d'informations, intégrant les deux modes d'accès que sont la formulation de requêtes (approche systèmes de recherche d'information) et la navigation (approche systèmes hypermédia). La motivation de cette étude repose sur la constatation que ces deux approches sont fortement complémentaires, les avantages de l'une compensant largement les limitations de l'autre. Classiquement, les modèles de recherche d'informations et d'hypermédia établissent une distinction entre les aspects structure des informations et les aspects représentation des connaissances. Cette distinction est, d'une part, de nature à limiter les possibilités de ces systèmes, et est un obstacle à l'intégration de ces deux modèles d'autre part. La base de notre approche d'intégration consiste tout d'abord à unifier ces deux types d'informations: une sémantique est attachée aux structures, et cette sémantique doit être explicitée et utilisée dans le processus d'accès à l'information, au même titre que les connaissances attachées au contenu de l'information. La définition formelle proposée du modèle intégré est largement fondée sur le formalisme des graphes conceptuels qui a été retenu pour représenter toutes les connaissances du système et pour réaliser les différentes opérations d'interrogation et de navigation propres aux deux approches. Une conclusion intéressante de cette démarche d'intégration est qu'elle conduit également à améliorer les deux modèles composants, par rapport à l'état de l'art. Une expérimentation du modèle proposé a conduit à la réalisation d'un prototype fondé sur O2 (SGBD Orienté Objet) et l'interface MOSAIC de WWW (World Wide Web), et les tests ont utilisé le corpus du système RIME (Recherche d'Informations MEdicales)

M.Sc. (Computer Science)
The purpose of this disssertation is to study methods to represent structures in three-dimensions. Due to the fact that chemical molecules are mostly complex three-dimensional structures, we used chemical molecules as our application domain. A literature study of current chemical information systems was undertaken. The whole spectrum of information systems was covered because almost all of these systems represent chemical molecules in one way or another. Various methods of three-dimensional structure representation were found in our literature study. All of these methods were discussed in the context of its own application domain. Structure graph grammars were examined and explained in detail. A small object-based system with structure graph grammars as the underlying principle was developed. We speculated on the use of such "intelligent" graph grammars in structure interpretation and identification. Further research in this area was also identified.

Research Doctorate - Doctor of Philosophy (PhD)
We study representations of numerical semigroups Σ by isometries on Hilbert space with commuting range projections. Our main theorem says that each such representation is unitarily equivalent to the direct sum of a representation by unitaries and a finite number of multiples of particular concrete representations by isometries. We use our main theorem to identify the faithful representations of the C*-algebra C*(Σ) generated by a universal isometric representation with commuting range projections, and also prove a structure theorem for C*(Σ). We also investigate the ideal structure of Exel's crossed product C₀(T)⋊_α,Lℕ. We give conditions describing precisely when C₀(T)⋊_α,Lℕ is simple. We provide a complete description of the gauge-invariant ideals of C₀(T)⋊_α,Lℕ, and give a condition which ensures that every ideal of C₀(T)⋊_α,Lℕ is gauge invariant. Under the assumption that Τ is second countable, we describe the primitive ideal structure of C₀(T)⋊_α,Lℕ.

Statistical analysis of networks has grown rapidly over the last few years with increasing number of applications. Graph-valued data carries additional information of dependencies which opens the possibility of modeling highly complex objects in vast number of fields such as biology (e.g. brain networks , fungi networks, genes co-expression), chemistry (e.g. molecules fingerprints), psychology (e.g. social networks) and many others (e.g. citation networks, word co-occurrences, financial systems, anomaly detection). While the inclusion of graph structure in the analysis can further help inference, simple statistical tasks in a network is very complex. For instance, the assumption of exchangeability of the nodes or the edges is quite strong, and it brings issues such as sparsity, size bias and poor characterization of the generative process of the data. Solutions to these issues include adding specific constraints and assumptions on the data generation process. In this work, we approach this problem by assuming graphs are globally sparse but locally dense, which allows exchangeability assumption to hold in local regions of the graph. We consider problems with two types of locality structure: block structure (also framed as multiple graphs or population of networks) and unstructured sparsity which can be seen as missing data. For the former, we developed a hypothesis testing framework for weighted aligned graphs; and a spectral clustering method for community detection on population of non-aligned networks. For the latter, we derive an efficient spectral clustering approach to learn the parameters of the zero inflated stochastic blockmodel. Overall, we found that incorporating multiple local dense structures leads to a more precise and powerful local and global inference. This result indicates that this general modeling scheme allows for exchangeability assumption on the edges to hold while generating more realistic graphs. We give theoretical conditions for our proposed algorithms, and we evaluate them on synthetic and real-world datasets, we show our models are able to outperform the baselines on a number of settings.

(in English): Conceptual graphs are a formal knowledge representation language introduced by John F. Sowa, an American specialist on Artificial Intelligence, at the end of the seventies. They are the synthesis of heuristic and formalistic approach to Artificial Intelligence and knowledge procession. They provide meaning and knowledge in form, which is logically precise, human- readable and untestable, and it is applicable in the computing domain in general. Conceptual graphs can be expressed through a first-order logic, which makes them a quality tool for intelligent reasoning. Their notation CGIF was standardised by norm ISO/IEC 24707:2007 as one of the three dialects of Common logic, which frames the set of logic based on logic. Conceptual graphs are also mappable to knowledge representation languages standardised for the Semantic Web; OWL and RDF (S). This work introduces the conceptual graph theory in the context of scientific fields like linguistics, logic and artificial intelligence. It represents the formalism proposed by John F. Sowa and some extensions that have emerged over the past decades, along with the need for improvements to the representational properties of graphs. Finally, the work provides an illustrative overview of the implementation and use of conceptual graphs in practice....

In the past little work has been done to characterize the models of various mereotopological systems. This thesis focuses on Asher and Vieu's first-order mereotopology which evolved from Clarke's Calculus of Individuals. Its soundness and completeness proofs with respect to a topological translation of the axioms provide only sparse insights into structural properties of the mereotopological models. To overcome this problem, we characterize these models with respect to mathematical structures with well-defined properties - topological spaces, lattices, and graphs. We prove that the models of the subtheory RT− are isomorphic to p-ortholattices (pseudocomplemented, orthocomplemented). Combining the advantages of lattices and graphs, we show how Cartesian products of finite p-ortholattices with one multiplicand being not uniquely complemented (unicomplemented) gives finite models of the full mereotopology. Our analysis enables a comparison to other mereotopologies, in particular to the RCC, of which lattice-theoretic characterizations exist.

This thesis deals with cohomologies on the symplectic quotient of a Frölicher space which is locally diffeomorphic to a Euclidean Frölicher subspace of Rn of constant dimension equal to n. The symplectic reduction under consideration in this thesis is an extension of the Marsden-Weinstein quotient (also called, the reduced space) well-known from the finite-dimensional smooth manifold case. That is, starting with a proper and free action of a Frölicher-Lie-group on a locally Euclidean Frölicher space of finite constant dimension, we study the smooth structure and the topology induced on a small subspace of the orbit space. It is on this topological space that we will construct selected cohomologies such as : sheaf cohomology, Alexander-Spanier cohomology, singular cohomology, ~Cech cohomology and de Rham cohomology. Some natural questions that will be investigated are for instance: the impact of the symplectic structure on these di erent cohomologies; the cohomology that will give a good description of the topology on the objects of category of Frölicher spaces; the extension of the de Rham cohomology theorem in order to establish an isomorphism between the five cohomologies. Beside the algebraic, topological and geometric study of these new objects, the thesis contains a modern formalism of Hamiltonian mechanics on the reduced space under symplectic and Poisson structures.
Mathematical Sciences
D. Phil. (Mathematics)