Positive Varieties of Lattice Languages
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918047379357696 |
|---|---|
| author | Inoue, Yusuke Komatsu, Yuji |
| author_facet | Inoue, Yusuke Komatsu, Yuji |
| contents | While a language assigns a value of either `yes' or `no' to each word, a lattice language assigns an element of a given lattice to each word. An advantage of lattice languages is that joins and meets of languages can be defined as generalizations of unions and intersections. This fact also allows for the definition of positive varieties -- classes closed under joins, meets, quotients, and inverse homomorphisms -- of lattice languages. In this paper, we extend Pin's positive variety theorem, proving a one-to-one correspondence between positive varieties of regular lattice languages and pseudo-varieties of finite ordered monoids. Additionally, we briefly explore algebraic approaches to finite-state Markov chains as an application of our framework. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_05824 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Positive Varieties of Lattice Languages Inoue, Yusuke Komatsu, Yuji Formal Languages and Automata Theory While a language assigns a value of either `yes' or `no' to each word, a lattice language assigns an element of a given lattice to each word. An advantage of lattice languages is that joins and meets of languages can be defined as generalizations of unions and intersections. This fact also allows for the definition of positive varieties -- classes closed under joins, meets, quotients, and inverse homomorphisms -- of lattice languages. In this paper, we extend Pin's positive variety theorem, proving a one-to-one correspondence between positive varieties of regular lattice languages and pseudo-varieties of finite ordered monoids. Additionally, we briefly explore algebraic approaches to finite-state Markov chains as an application of our framework. |
| title | Positive Varieties of Lattice Languages |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2506.05824 |