- -

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 completo del ítem

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

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/182919

Ficheros en el ítem

Thumbnail
Nombre: CanoCanteroMartin ...
Tamaño: 380.8Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir/Preview
[Cerrado]
Nombre: cano2021_article_ ...
Tamaño: 344.7Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor

Metadatos del ítem

Título: A positive extension of Eilenberg's variety theorem for non-regular languages
Autor: Cano Gómez, Antonio Cantero Delgado, Jesús Martínez-Pastor, Ana
Entidad UPV: Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada
Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació
Fecha difusión:
Resumen:
[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 ...[+]
Palabras clave: Monoids , Varieties , Formal languages
Derechos de uso: Reserva de todos los derechos
Fuente:
Applicable Algebra in Engineering Communication and Computing. (issn: 0938-1279 )
DOI: 10.1007/s00200-020-00414-2
Editorial:
Springer-Verlag
Versión del editor: https://doi.org/10.1007/s00200-020-00414-2
Código del Proyecto:
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/
info:eu-repo/grantAgreement/Generalitat Valenciana//Prometeo%2F2017%2F057//Grupos y semigrupos: estructura y aplicaciones/
Agradecimientos:
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).
Tipo: Artículo

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)

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)

Cadilhac, M., Krebs, A., McKenzie, P.: The algebraic theory of Parikh automata. Theory Comput. Syst. 62, 1241–1268 (2018) [+]
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)

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)

Cadilhac, M., Krebs, A., McKenzie, P.: The algebraic theory of Parikh automata. Theory Comput. Syst. 62, 1241–1268 (2018)

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)

Cano Gómez, A., Steinby, M.: Generalized contexts and n-ary syntactic semigroups of tree languages. Asian Eur. J. Math. 4, 49–79 (2011)

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)

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)

Cano Gómez, A., Pin, J.É.: Shuffle on positive varieties of languages. Theor. Comput. Sci. 312, 433–461 (2004)

Eilenberg, S.: Automata, Languages and Machines, vol. B. Academic Press, New York (1976)

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)

Krebs, A., Lange, K.J., Reifferscheid, S.: Characterizing $$TC^0$$ in terms of infinite groups. Theory Comput. Syst. 40(4), 303–325 (2007)

Pin, J.É.: Syntactic semigroups. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1 (chap. 10). Springer, Berlin (1997)

Pin, J.É.: Varieties of Formal Languages. Plenum Pub. Corp, New York (1986)

Pin, J.É.: A variety theorem without complementation. Russ. Math. (Iz. VUZ) 39, 74–83 (1995)

Pin, J.É., Straubing, H.: Some results on C-varieties. Theor. Inform. Appl. 39, 239–262 (2005)

Polák, L.: A classification of rational languages by semilattice-ordered monoids. Arch. Math. (Brno) 40, 395–406 (2004)

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)

Salamanca, J.: Unveiling Eilenberg-type Correspondences: Birkhoff’s theorem for (finite) algebras + duality. arXiv:1702.02822 (2017)

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)

Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh’auser, Boston (1994)

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)

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

[-]

recommendations

 

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

Mostrar el registro completo del ítem