Formal Languages and TQFTs with Defects

Luisa Boateng, Matilde Marcolli
12/12/2024
math-phcs.CLmath.QA

No confident code implementation found for this paper.

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ützenberger representation theorem, due to Melliès and Zeilberger. The corresponding TQFTs are then described as morphisms of colored operads on an operad of cobordisms with defects.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

The single-use restriction for register automata and transducers over infinite alphabets

75% match2024

Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory

74% match2025

A Framework for Quantum Finite-State Languages with Density Mapping

74% match1 repo2024

Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability

74% match2025

From Formal Language Theory to Statistical Learning: Finite Observability of Subregular Languages

73% match1 repo22025

Relative Prime Factorization and Finite-State Presentations under Fixed Finite-Monoid Observation

73% match2026

Cite this paper

@article{boateng2024formal,
  title  = {Formal Languages and TQFTs with Defects},
  author = {Luisa Boateng and Matilde Marcolli},
  year   = {2024},
  eprint = {2412.09688},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2412.09688v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2412.09688.svg)](https://codeofpaper.com/paper/2412.09688)

Discussion