Tensor Product Representations of Subregular Formal Languages

Jonathan Rawski

Tensor Product Representations of Subregular Formal Languages

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1908.08132 v1 pith:6QN67BYN submitted 2019-08-21 cs.FL cs.LO

Jonathan Rawski This is my paper · ORCID

classification cs.FLcs.LO

keywords languagessubregularmodelsstatementsstructurestensorapplicationapplied

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

read the original abstract

This paper provides a geometric characterization of subclasses of the regular languages. We use finite model theory to characterize objects like strings and trees as relational structures. Logical statements meeting certain criteria over these models define subregular classes of languages. The semantics of such statements can be compiled into tensor structures, using multilinear maps as function application for evaluation. This method is applied to consider two properly subregular languages over different string models.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Formal Languages and TQFTs with Defects
math-ph 2024-12 conditional novelty 6.0 of 10

A Boolean 1D TQFT-with-defects construction for regular languages is shown to be functorial under transducers and generalized to context-free grammars via an operadic Chomsky-Schützenberger theorem.

Pith tools