A New Graph Grammar Formalism for Robust Syntactic Pattern Recognition

• URL: http://arxiv.org/abs/2504.15975v2
• Date: Thu, 24 Apr 2025 10:39:43 GMT
• Title: A New Graph Grammar Formalism for Robust Syntactic Pattern Recognition
• Authors: Peter Fletcher,
• Abstract summary: It does not use production rules, like a conventional graph grammar, but represents the syntactic structure in a more direct and declarative way.<n>The grammar and the pattern are both represented as networks, and parsing is seen as the construction of a homomorphism from the pattern to the grammar.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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 is seen as the construction of a homomorphism from the pattern to the grammar. The grammars can represent iterative, hierarchical and nested recursive structure in more than one dimension. This supports a highly parallel style of parsing, in which all aspects of pattern recognition (feature detection, segmentation, parsing, filling in missing symbols, top-down and bottom-up inference) are integrated into a single process, to exploit the synergy between them. The emphasis of this paper is on underlying theoretical issues, but I also give some example runs to illustrate the error-tolerant parsing of complex recursively structured patterns of 50-1000 symbols, involving variability in geometric relationships, blurry and indistinct symbols, overlapping symbols, cluttered images, and erased patches.

Related papers

• Transformer-Based Models Are Not Yet Perfect At Learning to Emulate Structural Recursion [14.739369424331478]
  We introduce a general framework that nicely connects the abstract concepts of structural recursion in the programming language domain to sequence modeling problems and learned models' behavior. With our framework as a powerful conceptual tool, we identify different issues under various set-ups.
  arXiv  Detail & Related papers  (2024-01-23T18:07:38Z)
• SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
  We propose a generalization of graph isomorphism that allows one to check complex structural properties. This specification is given in the form of a Regular Graph Pattern (ReGaP), a special type of graph inspired by regular expressions. We propose a SAT-based algorithm for checking if a target graph matches a given ReGaP.
  arXiv  Detail & Related papers  (2023-12-15T18:12:44Z)
• Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
  Tasks that model the relation between pairs of tokens in a string are a vital part of understanding natural language. We show that these exhaustive comparisons can be avoided, and, moreover, the complexity can be reduced to linear by casting the relation between tokens as a partial order over the string. Our method predicts real numbers for each token in a string in parallel and sorts the tokens accordingly, resulting in total orders of the tokens in the string.
  arXiv  Detail & Related papers  (2023-05-24T11:47:35Z)
• Conversational Semantic Parsing using Dynamic Context Graphs [68.72121830563906]
  We consider the task of conversational semantic parsing over general purpose knowledge graphs (KGs) with millions of entities, and thousands of relation-types. We focus on models which are capable of interactively mapping user utterances into executable logical forms.
  arXiv  Detail & Related papers  (2023-05-04T16:04:41Z)
• TranSG: Transformer-Based Skeleton Graph Prototype Contrastive Learning with Structure-Trajectory Prompted Reconstruction for Person Re-Identification [63.903237777588316]
  Person re-identification (re-ID) via 3D skeleton data is an emerging topic with prominent advantages. Existing methods usually design skeleton descriptors with raw body joints or perform skeleton sequence representation learning. We propose a generic Transformer-based Skeleton Graph prototype contrastive learning (TranSG) approach with structure-trajectory prompted reconstruction.
  arXiv  Detail & Related papers  (2023-03-13T02:27:45Z)
• Polynomial Graph Parsing with Non-Structural Reentrancies [0.2867517731896504]
  Graph-based semantic representations are valuable in natural language processing. We introduce graph extension grammar, which generates graphs with non-structural reentrancies. We provide a parsing algorithm for graph extension grammars, which is proved to be correct and run in time.
  arXiv  Detail & Related papers  (2021-05-05T13:05:01Z)
• Compositional Generalization via Semantic Tagging [81.24269148865555]
  We propose a new decoding framework that preserves the expressivity and generality of sequence-to-sequence models. We show that the proposed approach consistently improves compositional generalization across model architectures, domains, and semantic formalisms.
  arXiv  Detail & Related papers  (2020-10-22T15:55:15Z)
• Inducing Alignment Structure with Gated Graph Attention Networks for Sentence Matching [24.02847802702168]
  This paper proposes a graph-based approach for sentence matching. We represent a sentence pair as a graph with several carefully design strategies. We then employ a novel gated graph attention network to encode the constructed graph for sentence matching.
  arXiv  Detail & Related papers  (2020-10-15T11:25:54Z)
• LogicalFactChecker: Leveraging Logical Operations for Fact Checking with Graph Module Network [111.24773949467567]
  We propose LogicalFactChecker, a neural network approach capable of leveraging logical operations for fact checking. It achieves the state-of-the-art performance on TABFACT, a large-scale, benchmark dataset.
  arXiv  Detail & Related papers  (2020-04-28T17:04:19Z)
• Graph-Structured Referring Expression Reasoning in The Wild [105.95488002374158]
  Grounding referring expressions aims to locate in an image an object referred to by a natural language expression. We propose a scene graph guided modular network (SGMN) to perform reasoning over a semantic graph and a scene graph. We also propose Ref-Reasoning, a large-scale real-world dataset for structured referring expression reasoning.
  arXiv  Detail & Related papers  (2020-04-19T11:00:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.