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
• 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

• Does Syntax Matter? A Graph-Augmented Variational Topic Model for Computational Social Sciences [51.56484100374058]
  This paper introduces the Structural Contextual Probabilistic Topic Model ( SCPTM), an architecture that incorporates syntactic dependency relations into topic inference.<n>We evaluate seven topic modeling techniques across four corpora differing in register and discourse structure.<n>Results show that SCPTM's neural architecture yields substantial gains in document-topic alignment over generative baselines.
  arXiv  Detail & Related papers  (2026-09-07T17:39:06Z)
• Token-to-Token Alignment of Text Embeddings for Semantic Blending [55.88554156801394]
  We introduce Token-to-Token alignment, a framework that establishes explicit semantic correspondence between tokens across prompts.<n>Our results show that text embedding spaces in text-to-image models implicitly encode a continuous semantic structure that becomes accessible once representations are properly aligned.
  arXiv  Detail & Related papers  (2026-06-22T23:54:40Z)
• Overcoming the Impedance Mismatch: A Theoretical Roadmap for Fusing Foundation Models and Knowledge Graphs [0.0]
  We formalize the underlying structural and geometric friction as the textitImpedance Mismatch.<n>We propose a rigorous theoretical roadmap to achieve true semantic fusion.<n>This framework paves the way for models that seamlessly fuse the precision of symbolic logic with the expressivity of parametric memory.
  arXiv  Detail & Related papers  (2026-04-21T17:30:15Z)
• StructCoh: Structured Contrastive Learning for Context-Aware Text Semantic Matching [10.000850856259866]
  StructCoh is a graph-enhanced contrastive learning framework.<n>A hierarchical contrastive objective enforces consistency at multiple granularities.<n>Experiments on three legal document matching benchmarks and academic plagiarism detection datasets demonstrate significant improvements.
  arXiv  Detail & Related papers  (2025-09-02T07:21:36Z)
• 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.