Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

A non-regular language of infinite trees that is recognized by a sort-wise finite Algebra

Uproszczony widok
dc.abstract.enω-clones are multi-sorted structures that naturally emerge as algebras for infinite trees, just as ω-semigroups are convenient algebras for infinite words. In the algebraic theory of languages, one hopes that a language is regular if and only if it is recognized by an algebra that is finite in some simple sense. We show that, for infinite trees, the situation is not so simple: there exists an ω-clone that is finite on every sort and finitely generated, but recognizes a non-regular language.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorKlin, Bartosz
dc.contributor.authorBojańczyk, Mikołaj
dc.date.accessioned2024-01-24T18:04:21Z
dc.date.available2024-01-24T18:04:21Z
dc.date.copyright2019-11-29
dc.date.issued2019
dc.description.accesstimeAT_PUBLICATION
dc.description.financeNie dotyczy
dc.description.number4
dc.description.versionFINAL_PUBLISHED
dc.description.volume14
dc.identifier.doi10.23638/LMCS-15(4:11)2019
dc.identifier.issn1860-5974
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/101735
dc.identifier.weblinkhttp://www.scopus.com/inward/record.url?eid=2-s2.0-85078705206&partnerID=MN8TOARS
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofLogical Methods in Computer Science
dc.relation.pages11:1–11:13
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleA non-regular language of infinite trees that is recognized by a sort-wise finite Algebra
dc.typeJournalArticle
dspace.entity.typePublication