- -

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

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

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

Mostrar el registro sencillo del ítem

Ficheros en el ítem

Thumbnail
Nombre: CanoCanteroMartin ...
Tamaño: 380.8Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir
[Cerrado]
Nombre: cano2021_article_ ...
Tamaño: 344.7Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor
dc.contributor.author Cano Gómez, Antonio es_ES
dc.contributor.author Cantero Delgado, Jesús es_ES
dc.contributor.author Martínez-Pastor, Ana es_ES
dc.date.accessioned 2022-05-25T18:04:05Z
dc.date.available 2022-05-25T18:04:05Z
dc.date.issued 2021-11 es_ES
dc.identifier.issn 0938-1279 es_ES
dc.identifier.uri http://hdl.handle.net/10251/182919
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 properties es_ES
dc.description.sponsorship The 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.language Inglés es_ES
dc.publisher Springer-Verlag es_ES
dc.relation.ispartof Applicable Algebra in Engineering Communication and Computing es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Monoids es_ES
dc.subject Varieties es_ES
dc.subject Formal languages es_ES
dc.subject.classification LENGUAJES Y SISTEMAS INFORMATICOS es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title A positive extension of Eilenberg's variety theorem for non-regular languages es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s00200-020-00414-2 es_ES
dc.relation.projectID info: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.projectID info:eu-repo/grantAgreement/Generalitat Valenciana//Prometeo%2F2017%2F057//Grupos y semigrupos: estructura y aplicaciones/ es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation Cano 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-2 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1007/s00200-020-00414-2 es_ES
dc.description.upvformatpinicio 553 es_ES
dc.description.upvformatpfin 573 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 32 es_ES
dc.description.issue 5 es_ES
dc.relation.pasarela S\400256 es_ES
dc.contributor.funder Generalitat Valenciana es_ES
dc.contributor.funder AGENCIA ESTATAL DE INVESTIGACION es_ES
dc.description.references Ballester-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.references Behle, 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.references Cadilhac, M., Krebs, A., McKenzie, P.: The algebraic theory of Parikh automata. Theory Comput. Syst. 62, 1241–1268 (2018) es_ES
dc.description.references Cano, 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.references Cano 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.references Chaubard, 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.references Cano 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.references Cano Gómez, A., Pin, J.É.: Shuffle on positive varieties of languages. Theor. Comput. Sci. 312, 433–461 (2004) es_ES
dc.description.references Eilenberg, S.: Automata, Languages and Machines, vol. B. Academic Press, New York (1976) es_ES
dc.description.references Klaedtke, 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.references Krebs, 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.references Pin, J.É.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1 (chap. 10). Springer, Berlin (1997) es_ES
dc.description.references Pin, J.É.: Varieties of Formal Languages. Plenum Pub. Corp, New York (1986) es_ES
dc.description.references Pin, J.É.: A variety theorem without complementation. Russ. Math. (Iz. VUZ) 39, 74–83 (1995) es_ES
dc.description.references Pin, J.É., Straubing, H.: Some results on C-varieties. Theor. Inform. Appl. 39, 239–262 (2005) es_ES
dc.description.references Polák, L.: A classification of rational languages by semilattice-ordered monoids. Arch. Math. (Brno) 40, 395–406 (2004) es_ES
dc.description.references Sakarovitch, 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.references Salamanca, J.: Unveiling Eilenberg-type Correspondences: Birkhoff’s theorem for (finite) algebras + duality. arXiv:1702.02822 (2017) es_ES
dc.description.references Steinby, 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.references Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh’auser, Boston (1994) es_ES
dc.description.references Straubing, 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.references Urbat, 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.05831 es_ES


Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem