Formal Languages and TQFTs with Defects

• URL: http://arxiv.org/abs/2412.09688v1
• Date: Thu, 12 Dec 2024 19:07:31 GMT
• Title: Formal Languages and TQFTs with Defects
• Authors: Luisa Boateng, Matilde Marcolli,
• Abstract summary: A construction that assigns a Boolean 1D TQFT with defects to a finite state automaton was recently developed by Gustafson, Im, Kaldawy, Khovanov, and Lihn. We show that the construction is functorial with respect to the category of finite state automata with transducers as morphisms.
• Score: 0.0
• License:
• Abstract: A construction that assigns a Boolean 1D TQFT with defects to a finite state automaton was recently developed by Gustafson, Im, Kaldawy, Khovanov, and Lihn. We show that the construction is functorial with respect to the category of finite state automata with transducers as morphisms. Certain classes of subregular languages correspond to additional cohomological structures on the associated TQFTs. We also show that the construction generalizes to context-free grammars through a categorical version of the Chomsky-Sch\"utzenberger representation theorem, due to Melli\`es and Zeilberger. The corresponding TQFTs are then described as morphisms of colored operads on an operad of cobordisms with defects.

Related papers

• Learning Syntax Without Planting Trees: Understanding When and Why Transformers Generalize Hierarchically [74.96551626420188]
  Transformers trained on natural language data have been shown to learn its hierarchical structure and generalize to sentences with unseen syntactic structures. We investigate sources of inductive bias in transformer models and their training that could cause such generalization behavior to emerge.
  arXiv  Detail & Related papers  (2024-04-25T07:10:29Z)
• Inducing Systematicity in Transformers by Attending to Structurally Quantized Embeddings [60.698130703909804]
  Transformers generalize to novel compositions of structures and entities after being trained on a complex dataset. We propose SQ-Transformer that explicitly encourages systematicity in the embeddings and attention layers. We show that SQ-Transformer achieves stronger compositional generalization than the vanilla Transformer on multiple low-complexity semantic parsing and machine translation datasets.
  arXiv  Detail & Related papers  (2024-02-09T15:53:15Z)
• Structural generalization is hard for sequence-to-sequence models [85.0087839979613]
  Sequence-to-sequence (seq2seq) models have been successful across many NLP tasks. Recent work on compositional generalization has shown that seq2seq models achieve very low accuracy in generalizing to linguistic structures that were not seen in training.
  arXiv  Detail & Related papers  (2022-10-24T09:03:03Z)
• On the Intersection of Context-Free and Regular Languages [71.61206349427509]
  We generalize the Bar-Hillel construction to handle finite-state automatons with $varepsilon$-arcs. We prove that our construction leads to a grammar that encodes the structure of both the input automaton and grammar while retaining the size of the original construction.
  arXiv  Detail & Related papers  (2022-09-14T17:49:06Z)
• Mixed-state TQFTs [0.0]
  We propose a generalization of Atiyah type TQFTs from pure states to mixed states. We define mixed-state TQFTs by replacing the target category Vec by QCS.
  arXiv  Detail & Related papers  (2021-10-24T13:53:38Z)
• A CCG-Based Version of the DisCoCat Framework [1.7219938668142956]
  The DisCoCat model is used to study compositional aspects of language at the level of semantics. In this paper we reformulating DisCoCat as a passage from Combinatory Categorial Grammar (CCG) We show that standard categorial grammars can be expressed as a biclosed category, where all rules emerge as currying/uncurrying the identity. We then proceed to model permutation-inducing rules by exploiting the symmetry of the compact closed category encoding the word meaning.
  arXiv  Detail & Related papers  (2021-05-17T10:32:18Z)
• Constructing a Family Tree of Ten Indo-European Languages with Delexicalized Cross-linguistic Transfer Patterns [57.86480614673034]
  We formalize the delexicalized transfer as interpretable tree-to-string and tree-to-tree patterns. This allows us to quantitatively probe cross-linguistic transfer and extend inquiries of Second Language Acquisition.
  arXiv  Detail & Related papers  (2020-07-17T15:56:54Z)
• Models of zero-range interaction for the bosonic trimer at unitarity [91.3755431537592]
  We present the construction of quantum Hamiltonians for a three-body system consisting of identical bosons mutually coupled by a two-body interaction of zero range. For a large part of the presentation, infinite scattering length will be considered.
  arXiv  Detail & Related papers  (2020-06-03T17:54:43Z)
• A Frobenius Algebraic Analysis for Parasitic Gaps [4.254099382808598]
  We identify two types of parasitic gapping where the duplication of semantic content can be confined to the lexicon. For parasitic gaps affecting arguments of the same predicate, the polymorphism is associated with the lexical item that introduces the primary gap. A compositional translation relates syntactic types and derivations to the interpreting compact closed category of finite dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-05-12T09:36:15Z)
• Ground Subspaces of Topological Phases of Matter as Error Correcting Codes [0.9306768284179177]
  We prove that a lattice implementation of the disk axiom and annulus axiom in TQFTs is essentially the equivalence of TQO1 and TQO2 conditions. We propose to characterize topological phases of matter via error correcting properties, and refer to gapped fracton models as lax-topological.
  arXiv  Detail & Related papers  (2020-04-24T20:38:10Z)

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.