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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Positive Varieties of Lattice Languages

  • Yusuke Inoue,
  • Yuji Komatsu

摘要

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.