Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657699 | Theoretical Computer Science | 2005 | 35 Pages |
Abstract
Pin's variety theorem for positive varieties of string languages and varieties of finite ordered semigroups is proved for trees, i.e., a bijective correspondence between positive varieties of tree languages and varieties of finite ordered algebras is established. This, in turn, is extended to generalized varieties of finite ordered algebras, which corresponds to Steinby's generalized variety theorem. Also, families of tree languages and classes of ordered algebras that are definable by ordered (syntactic or translation) monoids are characterized.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Tatjana PetkoviÄ, Saeed Salehi,