Lasso Language

Definition

A lasso is a pair $(u,v)\in {\Sigma }^{\ast }\times {\Sigma }^{+}$ consisting of a “spoke” $u$ and a non-empty “loop” $v$. The lasso $(u,v)$ represents the ultimately periodic infinite word $u{v}^{\omega }$.

A Lasso Language $L$ is a subset of lassos: $L\subseteq {\Sigma }^{\ast }\times {\Sigma }^{+}$

Classes of Lasso Languages

According to Mike Cruchten, a lasso language $L$ is:

• Rational: if there exists a finite Lasso Automaton $\mathcal{A}$ such that $L=L(\mathcal{A})$.
• Regular: if it can be defined by a Rational Lasso Expression (an extension of regular expressions to pairs).

Theorems

• Kleene Theorem for Lassos: A lasso language is rational iff it is regular.
• Correspondence: A language of infinite words is omega-regular iff its set of lassos is accepted by a saturated lasso automaton (also called an $\Omega$-automaton).

Remarks

Seen at Midlands Graduate School in the Foundations of Computing Science 2025. Mike Cruchten’s talk on Automata Theory.