23 papers · ranked by Valyu relevance
Jayakrishna Vijayakumar, Lisa Mathew
Graph grammars form an interesting area of research because of their versatility in modelling diverse situations with graphs as the structures which are to be manipulated. A new class of graph grammars, nc-eNCE Graph Grammars has been introduced recently with an aim of restricting the order of application of graph…
Frank Julca-Aguilar, Harold Mouchère, Christian Viard-Gaudin, Nina S. T. Hirata
'Nina S. T. Hirata'] Abstract—We propose a new framework for the recognition of online handwritten graphics. Three main features of the framework are its ability to treat symbol and structural level information in an integrated way, its flexibility with respect to different families of graphics, and means to control…
Mark Chimes, Radu Iosif, Florian Zuleger
Hyperedge-Replacement grammars (HR) have been introduced by Courcelle in order to extend the notion of context-free sets from words and trees to graphs of bounded tree-width. While for words and trees the syntactic restrictions that guarantee that the associated languages of words resp. trees are regular - and hence…
Yi Wang, XiaoQin Zeng, Han Ding, Rongrong Ji
The parsing problem is one of the key problems of graph grammars. The typical parsing algorithm uses the bottom-up method. The time-complexity of this method is high, and it is difficult to apply. In order to reduce the time-complexity, this paper uses the top-down method for parsing. This method avoids the subgraph…
Aleks Kissinger, Vladimir Zamdzhiev
String diagrams are a powerful tool for reasoning about composite structures in symmetric monoidal categories. By representing string diagrams as graphs, equational reasoning can be done automatically by double-pushout rewriting. !-graphs give us the means of expressing and proving properties about whole families of…
Peter Fletcher
I introduce a formalism for representing the syntax of recursively structured graph-like patterns. It does not use production rules, like a conventional graph grammar, but represents the syntactic structure in a more direct and declarative way. The grammar and the pattern are both represented as networks, and parsing…
Authors not listed
Digital twins are virtual companions for the design, scale-up, and control of chemical processes. Equipping digital twins with mechanistic models of their mirrored unit operation expands their range of applicability compared to pure data-driven models. As constructing mechanistic models requires time, effort, and…
Jayakrishna Vijayakumar, Lisa Mathew
In the study of automata and grammars, closure properties of the associated languages have been studied extensively. In particular, closure properties of various types of graph grammars have been examined in (Rozenberg and Welzl, Inf. and Control,1986) and (Rozenberg and Welzl, Acta Informatica,1986). In this paper we…
Eric Mjolsness
Stochastic and Dynamical Graph Grammar Rule Operators in Biological Morphodynamics Authors: ['Eric Mjolsness'] Many emergent, non-fundamental models of complex systems can be described naturally by the temporal evolution of spatial structures with some nontrivial discretized topology, such as a graph with suitable…
Richard Apodaca
Despite its widespread use, Simplified Molecular Input Line Entry System (SMILES) remains underspecified. The lack of a detailed specification encourages improvisation by software developers, complicates data standardization efforts, and undermines extension development. Balsa, a reformulation of SMILES, addresses…
Peter Heringer, Daniel Doerr
Pangenome graphs offer a compact and comprehensive representation of genomic diversity, improving tasks such as variant calling, genotyping, and other downstream analyses. Although the underlying graph structures scale sublinearly with the number of haplotypes, the widely used GFA file format suffers from rapidly…
Kaixuan Zhang, Qinglong Wang, C. Lee Giles
Recently, there has been a resurgence of formal language theory in deep learning research. However, most research focused on the more practical problems of attempting to represent symbolic knowledge by machine learning. In contrast, there has been limited research on exploring the fundamental connection between them.…
Authors not listed
RNA molecules fold into complex three-dimensional structures that determine their function. A wide range of mathematical frameworks, such as chord diagrams, fatgraphs, and context-free grammars, have been used to represent these structures; however, these models have largely been developed from mathematical motivations…
Guillaume Bonfante, Bruno Guillaume
So far, a very large amount of work in Natural Language Processing (NLP) rely on trees as the core mathematical structure to represent linguistic informations (e.g. in Chomsky's work). However, some linguistic phenomena do not cope properly with trees. In a former paper, we showed the benefit of encoding linguistic…
Johannes T. Margraf, Zachary W. Ulissi, Yousung Jung, Karsten Reuter
The discovery of new catalytically active materi- als is one of the holy grails of computational chemistry as it has the potential to accelerate the adoption of renewable energy sources and reduce the energy consumption of chemical industry. Indeed, heterogeneous catalysts are essential for the production of synthetic…
Neil Cohn, Joost Schilperoord
Language is typically embedded in multimodal communication, yet models of linguistic competence do not often incorporate this complexity. Meanwhile, speech, gesture, and/or pictures are each considered as indivisible components of multimodal messages. Here, we argue that multimodality should not be characterized by…
Lucas Y. Tian, Daniel J. Hanuska, Kedar Garzón Gupta, Yue Liu + 3 more
Humans and other animals can solve new problems, even on the first attempt. This capacity to generate novel problem-solving behavior has been hypothesized to depend on brain mechanisms for recombining units of knowledge using systems of procedural rules, or grammars. Yet, whether and how the brain represents and…
Remi van Trijp, Katrien Beuls, Paul Van Eecke, Andrew Kehler
Since its inception in the mid-eighties, the field of construction grammar has been steadily growing and constructionist approaches to language have by now become a mainstream paradigm for linguistic research. While the construction grammar community has traditionally focused on theoretical, experimental and…
Kuan-Hao Chao, Pei-Wei Chen, Sanjit A. Seshia, Ben Langmead
A Wheeler graph represents a collection of strings in a way that is particularly easy to index and query. Such a graph is a practical choice for representing a graph-shaped pangenome, and it is the foundation for current graph-based pangenome indexes. However, there are no practical tools to visualize or to check…
Tom C. Freeman, Sebastian Horsewell, Anirudh Patir, Josh Harling-Lee + 5 more
Quantitative and qualitative data derived from the analysis of genomes, genes, proteins or metabolites from tissue or cells are currently generated in huge volumes during biomedical research. Graphia is an open-source platform created for the graph-based analysis of such complex data, e.g. transcriptomics, proteomics…
Authors not listed
A directed graph (or digraph) consists of a finite vertex set 𝑉 and a set of ordered edges 𝐸 ⊆ 𝑉 × 𝑉, each edge (𝑢, 𝑣) indicating a one-way connection from 𝑢 (source) to 𝑣 (target). A bidirected graph is a generalization of an undirected graph where each edge is assigned a direction at each of its endpoints…
Erik Garrison, Jouni Sirén, Adam M. Novak, Glenn Hickey + 6 more
Reference genomes guide our interpretation of DNA sequence data. However, conventional linear references are fundamentally limited in that they represent only one version of each locus, whereas the population may contain multiple variants. When the reference represents an individual’s genome poorly, it can impact read…
Authors not listed
Curried functions provide a systematic way of transforming multi-argument functions into nested singleargument functions. This transformation allows partial application and supports many central principles of functional programming. Their extension, called curried 𝑘-ary functions, naturally generalizes the familiar…