A positive extension of Eilenberg's variety theorem for non-regular languages

Vista sencilla de ítem
dc.contributor.affiliationDepartamento de Matemática Aplicada
dc.contributor.affiliationInstituto Universitario de Matemática Pura y Aplicada
dc.contributor.affiliationEscuela Técnica Superior de Ingeniería Informática
dc.contributor.authorCano Gómez, Antonioes_ES
dc.contributor.authorCantero Delgado, Jesúses_ES
dc.contributor.authorMartínez-Pastor, Ana
dc.contributor.funderGeneralitat Valencianaes_ES
dc.contributor.funderAGENCIA ESTATAL DE INVESTIGACIONes_ES
dc.date.accessioned2022-05-25T18:04:05Z
dc.date.available2022-05-25T18:04:05Z
dc.date.issued2021-11es_ES
dc.description.abstract[EN] In this paper we go further with the study initiated by Behle, Krebs and Reifferscheid (in: Proceedings CAI 2011, Lecture Notes in Computer Science, vol 6742, pp 97-114, 2011), who gave an Eilenberg-type theorem for non-regular languages via typed monoids. We provide a new extension of that result, inspired by the one carried out by Pin in the regular case in 1995, who considered classes of languages not necessarily closed under complement. We introduce the so-called positively typed monoids, and give a correspondence between varieties of such algebraic structures and positive varieties of possibly non-regular languages. We also prove a similar result for classes of languages with weaker closure propertiesen_EN
dc.description.accrualMethodSes_ES
dc.description.bibliographicCitationCano Gómez, A.; Cantero Delgado, J.; Martínez-Pastor, A. (2021). A positive extension of Eilenberg's variety theorem for non-regular languages. Applicable Algebra in Engineering Communication and Computing. 32(5):553-573. https://doi.org/10.1007/s00200-020-00414-2es_ES
dc.description.issue5es_ES
dc.description.referencesBallester-Bolinches, A., Pin, J.É., Soler-Escrivà, X.: Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited. Forum Math. 26(6), 1737–1761 (2014)es_ES
dc.description.referencesBehle, C., Krebs, A., Reifferscheid, S.: Typed monoids—an Eilenberg-like theorem for non regular languages. In: Proceedings CAI 2011. Lecture Notes in Computer Science, vol. 6742, pp. 97–114 (2011)es_ES
dc.description.referencesCadilhac, M., Krebs, A., McKenzie, P.: The algebraic theory of Parikh automata. Theory Comput. Syst. 62, 1241–1268 (2018)es_ES
dc.description.referencesCano, A., Jurvanen, E.: Varieties of languages and frontier check. In: Proceedings of 13th International Conference on Automata and Formal Languages AFL2011, pp. 153–167 (2011)es_ES
dc.description.referencesCano Gómez, A., Steinby, M.: Generalized contexts and n-ary syntactic semigroups of tree languages. Asian Eur. J. Math. 4, 49–79 (2011)es_ES
dc.description.referencesChaubard, L., Pin, J.É., Straubing, H.: First order formulas with modular predicates. In: Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science (LICS 2006), pp. 211–220. IEEE (2006)es_ES
dc.description.referencesCano Gómez, A.: Semigroupes ordonnés et opérations sur les langages rationnels. Ph.D. Thesis, Université Paris 7 and Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia (2003)es_ES
dc.description.referencesCano Gómez, A., Pin, J.É.: Shuffle on positive varieties of languages. Theor. Comput. Sci. 312, 433–461 (2004)es_ES
dc.description.referencesEilenberg, S.: Automata, Languages and Machines, vol. B. Academic Press, New York (1976)es_ES
dc.description.referencesKlaedtke, F., Rueß, H.: Monadic second-order logics with cardinalities. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) Automata, Languages and Programming. ICALP 2003. Lect. Notes Comput. Sci., vol. 2719, pp. 681–696. Springer, Heidelberg (2003)es_ES
dc.description.referencesKrebs, A., Lange, K.J., Reifferscheid, S.: Characterizing $$TC^0$$ in terms of infinite groups. Theory Comput. Syst. 40(4), 303–325 (2007)es_ES
dc.description.referencesPin, J.É.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1 (chap. 10). Springer, Berlin (1997)es_ES
dc.description.referencesPin, J.É.: Varieties of Formal Languages. Plenum Pub. Corp, New York (1986)es_ES
dc.description.referencesPin, J.É.: A variety theorem without complementation. Russ. Math. (Iz. VUZ) 39, 74–83 (1995)es_ES
dc.description.referencesPin, J.É., Straubing, H.: Some results on C-varieties. Theor. Inform. Appl. 39, 239–262 (2005)es_ES
dc.description.referencesPolák, L.: A classification of rational languages by semilattice-ordered monoids. Arch. Math. (Brno) 40, 395–406 (2004)es_ES
dc.description.referencesSakarovitch, J.: An algebraic framework for the study of the syntactic monoids application to the group languages. In: Mazurkiewic, A. (ed.) MFCS, pp. 510–516. Springer, Heidelberg (1976)es_ES
dc.description.referencesSalamanca, J.: Unveiling Eilenberg-type Correspondences: Birkhoff’s theorem for (finite) algebras + duality. arXiv:1702.02822 (2017)es_ES
dc.description.referencesSteinby, M.: A theory of tree language varieties. In: Nivat, M., Podelski, A. (eds.) Tree Automata and Languages, pp. 57–81. North-Holland, Amsterdam (1992)es_ES
dc.description.referencesStraubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh’auser, Boston (1994)es_ES
dc.description.referencesStraubing, H.: On logical descriptions of regular languages. In: Rajsbaum, S. (ed.) LATIN 2002. Lect. Notes Comput. Sci., vol. 2286, pp. 528–538. Springer, Berlin (2002)es_ES
dc.description.referencesUrbat, H., Admek, J., Chen, L., Milius, S.: Eilenberg theorems for free. In: Larsen, K.M., Bodlaender, H.L., Raskin, J.F. (eds.) MFCS 2017, vol. 83, pp. 43:1–43:15. LIPIcs, Leibnitz (2017). arXiv:1602.05831es_ES
dc.description.sponsorshipThe third author is supported by Proyecto PGC2018-096872-B-100-AR, Agencia Estatal de Investigacion (Spain), and by Proyecto Prometeo/2017/057, Generalitat Valenciana (Spain).es_ES
dc.description.upvformatpfin573es_ES
dc.description.upvformatpinicio553es_ES
dc.description.volume32es_ES
dc.identifier.doi10.1007/s00200-020-00414-2es_ES
dc.identifier.issn0938-1279es_ES
dc.identifier.urihttps://riunet.upv.es/handle/10251/182919
dc.languageIngléses_ES
dc.publisherSpringer-Verlages_ES
dc.relation.ispartofApplicable Algebra in Engineering Communication and Computinges_ES
dc.relation.pasarelaS\400256es_ES
dc.relation.projectIDinfo:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PGC2018-096872-B-I00/ES/GRUPOS, ESTRUCTURA LOCAL-GLOBAL E INVARIANTES NUMERICOS/es_ES
dc.relation.projectIDinfo:eu-repo/grantAgreement/GVA//Prometeo%2F2017%2F057//Grupos y semigrupos: estructura y aplicaciones/es_ES
dc.relation.publisherversionhttps://doi.org/10.1007/s00200-020-00414-2es_ES
dc.relation.references10.1515/forum-2012-0055es_ES
dc.relation.references10.1007/978-3-642-21493-6_6es_ES
dc.relation.references10.1007/s00224-017-9817-2es_ES
dc.relation.references10.1142/S179355711100006Xes_ES
dc.relation.references10.1016/j.tcs.2003.10.034es_ES
dc.relation.references10.1007/3-540-45061-0_54es_ES
dc.relation.references10.1007/s00224-006-1310-2es_ES
dc.relation.references10.1007/978-3-642-59136-5_10es_ES
dc.relation.references10.1007/978-1-4613-2215-3es_ES
dc.relation.references10.1051/ita:2005014es_ES
dc.relation.references10.1007/978-1-4612-0289-9es_ES
dc.relation.references10.1007/3-540-45995-2_46es_ES
dc.rightsReserva de todos los derechoses_ES
dc.rights.accessRightsAbiertoes_ES
dc.subjectMonoidses_ES
dc.subjectVarietieses_ES
dc.subjectFormal languageses_ES
dc.subject.classificationLENGUAJES Y SISTEMAS INFORMATICOSes_ES
dc.subject.classificationMATEMATICA APLICADAes_ES
dc.titleA positive extension of Eilenberg's variety theorem for non-regular languageses_ES
dc.typeArtículoes_ES
dc.type.versioninfo:eu-repo/semantics/publishedVersiones_ES
dspace.entity.typePublication
person.identifier2006
person.identifier.orcid0000-0002-0208-4098
relation.isAuthorOfPublication824f0995-2230-48f3-b10f-665d29e7372b
relation.isAuthorOfPublication.latestForDiscovery824f0995-2230-48f3-b10f-665d29e7372b
relation.isOrgUnitOfPublication1062a9b0-be7f-4afa-a1a1-1bbd944e9165
relation.isOrgUnitOfPublication7e7e57e7-7dd0-4216-b896-7a30ad9dcac3
relation.isOrgUnitOfPublicationd307086e-520c-4cdc-8116-d7178d71bfdc
relation.isOrgUnitOfPublication.latestForDiscovery1062a9b0-be7f-4afa-a1a1-1bbd944e9165
upv.uuid1128d573-9c7b-4728-a9b9-e5f827a648c8es_ES

Archivos

Bloque original

Mostrando 1 - 2 de 2
Miniatura
Nombre:
CanoCanteroMartinez-Pastor - A positive extension of Eilenbergs variety theorem for non-regular l....pdf
Tamaño:
380.88 KB
Formato:
Adobe Portable Document Format
Descripción:
Versión del Autor.
[object Object] Descargar
Miniatura
Nombre:
cano2021_article_apositiveextensionofeilenbergs.pdf
Tamaño:
344.8 KB
Formato:
Adobe Portable Document Format
Descripción:
Versión editorial
Descargar

Colecciones

Artículos, conferencias, monografías
OpenAIRE (Open Access Infrastructure for Research in Europe)