TY - JOUR AU - Dömösi, Pál Béla AU - Fazekas, S AU - Ito, M TI - On Chomsky Hierarchy of Palindromic Languages JF - ACTA CYBERNETICA J2 - ACTA CYBERN-SZEGED VL - 22 PY - 2016 IS - 3 SP - 703 EP - 713 PG - 11 SN - 0324-721X DO - 10.14232/actacyb.22.3.2016.10 UR - https://m2.mtmt.hu/api/publication/3320971 ID - 3320971 AB - The characterization of the structure of palindromic regular and palindromic context-free languages is described by S. Horvath, J. Karhumaki, and J. Kleijn in 1987. In this paper alternative proofs are given for these characterizations. LA - English DB - MTMT ER - TY - JOUR AU - Horváth, Géza AU - Nagy, Benedek TI - Pumping lemmas for linear and nonlinear context-free languages JF - ACTA UNIVERSITATIS SAPIENTIAE INFORMATICA J2 - ACTA UNIV SAP INFORM VL - 2 PY - 2010 IS - 2 SP - 194 EP - 209 PG - 16 SN - 1844-6086 UR - https://m2.mtmt.hu/api/publication/2399329 ID - 2399329 LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Horváth, Géza AU - Vuillon, Laurent TI - On the Shyr–Yu theorem JF - THEORETICAL COMPUTER SCIENCE J2 - THEOR COMPUT SCI VL - 410 PY - 2009 IS - 47 SP - 4874 EP - 4877 PG - 4 SN - 0304-3975 DO - 10.1016/j.tcs.2009.06.039 UR - https://m2.mtmt.hu/api/publication/2399325 ID - 2399325 N1 - Cited By :4 Export Date: 8 June 2023 CODEN: TCSCD Correspondence Address: Vuillon, L.; Laboratoire de Mathématiques, , 73376 Le Bourget du Lac, France; email: Laurent.Vuillon@univ-savoie.fr LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Marcus, S AU - Ito, M TI - Marcus Contextual Languages Consisting of Primitive Words JF - DISCRETE MATHEMATICS J2 - DISCRETE MATH VL - 308 PY - 2008 IS - 21 SP - 4877 EP - 4881 PG - 5 SN - 0012-365X DO - 10.1016/j.disc.2007.09.006 UR - https://m2.mtmt.hu/api/publication/1130593 ID - 1130593 LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Horváth, Géza TI - Alternative proof of the Lyndon-Schützenberger theorem JF - THEORETICAL COMPUTER SCIENCE J2 - THEOR COMPUT SCI VL - 366 PY - 2006 IS - 3 SP - 194 EP - 198 PG - 5 SN - 0304-3975 DO - 10.1016/j.tcs.2006.08.023 UR - https://m2.mtmt.hu/api/publication/1130216 ID - 1130216 AB - Some observations on products of primitive words are discussed. By these results, alternative proof is given for the Lyndon-Schützenberger Theorem, which says that every solution of the equation a(m)b(n)=c(k) over Sigma* is trivial. (c) 2006 Elsevier B.V. All rights reserved. LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Horváth, Géza AU - Ito, Masami AU - Shikishima-Tsuji, Kayoko TI - Some periodicity of words and Marcus contextual grammars JF - VIETNAM JOURNAL OF MATHEMATICS J2 - VIETNAM J MATH VL - 34 PY - 2006 IS - 4 SP - 381 EP - 387 PG - 7 SN - 2305-221X UR - https://m2.mtmt.hu/api/publication/2399324 ID - 2399324 LA - English DB - MTMT ER - TY - JOUR AU - Horváth, Géza TI - New Pumping Lemma for Non-Linear Context-Free Languages (Algorithmic problems in algebra, languages and computation systems) JF - SURIKAISEKIKENKYUSHO KOKYUROKU / RIMS KOKYUROKU J2 - RIMS KOKYUROKU VL - 1503 PY - 2006 SP - 160 EP - 163 PG - 4 SN - 1880-2818 UR - https://m2.mtmt.hu/api/publication/2399331 ID - 2399331 LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Martin-Vide, C AU - Mateescu, A TI - On polyslender context-free languages JF - PUBLICATIONES MATHEMATICAE DEBRECEN J2 - PUBL MATH DEBRECEN VL - 66 PY - 2005 IS - 1-2 SP - 1 EP - 15 PG - 15 SN - 0033-3883 UR - https://m2.mtmt.hu/api/publication/1130215 ID - 1130215 AB - A. Szilard, S. Yu, K. Zhang, and J. Shallit showed that for any positive integer k, a regular language is k-polyslender if and only if it is a finite union of (k + 1)-multiple loop languages. M. Latteux and G, Thierrin and later, independently, D. Raz proved that the family of polyslender context-free languages is bounded. Polyslender context-free languages are also characterized by L. Ilie, G. Rozenberg and A. Salomaa. In this paper, we continue this line of research. LA - English DB - MTMT ER - TY - CONF AU - Dömösi, Pál Béla AU - Horváth, Géza ED - Ésik, Zoltán ED - Fülöp, Zoltán TI - On products of primitive words T2 - Automata and Formal Languages PB - University of Szeged, Institute of Informatics C1 - Szeged PY - 2005 SP - 112 EP - 121 PG - 10 UR - https://m2.mtmt.hu/api/publication/1130306 ID - 1130306 LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Horváth, Géza AU - Ito, M TI - A small hierarchy of languages consisting of non-primitive words JF - PUBLICATIONES MATHEMATICAE DEBRECEN J2 - PUBL MATH DEBRECEN VL - 64 PY - 2004 IS - 3-4 SP - 261 EP - 267 PG - 7 SN - 0033-3883 UR - https://m2.mtmt.hu/api/publication/1130211 ID - 1130211 AB - Context-free languages consisting of non-primitive words have been characterized by M. Ito and M. Katsura in 1988. In this paper we show that the same type of characterization can be given for linear, respectively, regular languages consisting of non-primitive words. The observation completes our knowledge on the structure of different languages of non-primitive words. LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Martin-Vide, C AU - Mitrana, V TI - Remarks on sublanguages consisting of primitive words of slender regular and context-free languages JF - LECTURE NOTES IN COMPUTER SCIENCE J2 - LECT NOTES COMPUT SC VL - 3113 PY - 2004 SP - 60 EP - 67 PG - 8 SN - 0302-9743 DO - 10.1007/b98751#page=69 UR - https://m2.mtmt.hu/api/publication/1130212 ID - 1130212 AB - In this note we investigate the languages obtained by intersecting slender regular or context-free languages with the set of all primitive Words over the common alphabet. We prove that. these languages axe also re gular, and, respectively, context-free. The statement does not hold anymore for either regular or context-free languages. Moreover, the set of all non-primitive words of a slender context-free language is still context-free. Some possible directions for further research are finally discussed. LA - English DB - MTMT ER - TY - JOUR AU - Horváth, Géza TI - Small Grammars and Primitive Words (Algebraic Systems, Formal Languages and Conventional and Unconventional Computation Theory) JF - SURIKAISEKIKENKYUSHO KOKYUROKU / RIMS KOKYUROKU J2 - RIMS KOKYUROKU VL - 1366 PY - 2004 SP - 62 EP - 72 PG - 11 SN - 1880-2818 UR - https://m2.mtmt.hu/api/publication/2847549 ID - 2847549 LA - English DB - MTMT ER - TY - CHAP AU - Dömösi, Pál Béla AU - Kudlek, M ED - Ito, Masami ED - Imaoka, Teruo TI - An improvement of iteration lemmata for context-free languages T2 - Words, languages and combinatorics III. PB - World Scientific CY - Singapore SN - 9789810249489 PY - 2003 SP - 185 EP - 191 PG - 7 DO - 10.1142/4959 UR - https://m2.mtmt.hu/api/publication/1130311 ID - 1130311 LA - English DB - MTMT ER - TY - CHAP AU - Dömösi, Pál Béla AU - Horváth, S AU - Ito, M AU - Katsura, M ED - Csuhaj-Varjú, Erzsébet ED - Kintala, C ED - Wotschke, D ED - Vaszil, György TI - Some Remarks on Primitive Words and Palindromes T2 - 5th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2003 PB - MTA Számítástechnikai és Automatizálási Kutatóintézet CY - Budapest SN - 9633113563 PY - 2003 SP - 245 EP - 254 PG - 10 UR - https://m2.mtmt.hu/api/publication/3323447 ID - 3323447 LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Kudlek, M TI - Iteration lemmata for context-free and linear indexed languages JF - PUBLICATIONES MATHEMATICAE DEBRECEN J2 - PUBL MATH DEBRECEN VL - 60 PY - 2002 SP - 551 EP - 568 PG - 18 SN - 0033-3883 UR - https://m2.mtmt.hu/api/publication/1130323 ID - 1130323 LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Okawa, S TI - A Chomsky-Schützenberger-Stanley type characterization of the class of slender context-free languages JF - ACTA CYBERNETICA J2 - ACTA CYBERN-SZEGED VL - 15 PY - 2001 IS - 1-2 SP - 25 EP - 32 PG - 8 SN - 0324-721X UR - https://m2.mtmt.hu/api/publication/1130343 ID - 1130343 LA - English DB - MTMT ER - TY - CHAP AU - Dömösi, Pál Béla AU - Ito, M ED - Martín-Vide, C ED - Mitrana, V TI - Multiple keyword patterns in context-free languages T2 - Where mathematics, computer science, linguistics and biology meet. Essays in honour of Gheorghe Paun PB - Kluwer Academic Publishers CY - Dordrecht PY - 2001 SP - 237 EP - 241 PG - 5 UR - https://m2.mtmt.hu/api/publication/1130340 ID - 1130340 LA - English DB - MTMT ER - TY - CHAP AU - Dömösi, Pál Béla ED - Kiyoshi, Iseki ED - Jair, Minoro Abe ED - Shōtarō, Tanaka TI - Some of my favourite unsolved problems T2 - Unsolved problems on mathematics for the 21st century PB - IOS Press CY - Amsterdam CY - Tokyo CY - Washington DC PY - 2001 SP - 159 EP - 168 PG - 10 UR - https://m2.mtmt.hu/api/publication/1130335 ID - 1130335 LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla TI - Unusual algorithms for lexicographical enumeration JF - ACTA CYBERNETICA J2 - ACTA CYBERN-SZEGED VL - 14 PY - 2000 IS - 3 SP - 461 EP - 468 PG - 8 SN - 0324-721X UR - https://m2.mtmt.hu/api/publication/1130344 ID - 1130344 LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Okawa, S AU - Hirose, S TI - A Chomsky and Stanley type homomorphic characterization of the class of linear languages JF - BULLETIN OF THE EUROPEAN ASSOCIATION FOR THEORETICAL COMPUTER SCIENCE J2 - BULL EATCS VL - 68 PY - 1999 SP - 151 EP - 152 PG - 2 SN - 0252-9742 UR - https://m2.mtmt.hu/api/publication/1130345 ID - 1130345 LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Kudlek, M TI - Strong iteration lemmata for regular, linear, context-free, and linear indexed languages JF - LECTURE NOTES IN COMPUTER SCIENCE J2 - LECT NOTES COMPUT SC VL - 1684 PY - 1999 SP - 226 EP - 233 PG - 8 SN - 0302-9743 UR - https://m2.mtmt.hu/api/publication/1130207 ID - 1130207 AB - New iteration lemmata are presented, generalizing most of the known iteration lemmata for regular, linear, context-free, and linear indexed languages. LA - English DB - MTMT ER - TY - CHAP AU - Dömösi, Pál Béla AU - Ito, M ED - Shum, Kar Ping ED - [et, al] TI - Characterization of languages by lengths of their subwords T2 - Semigroups : Papers from the international conference on semigroups and its related topics PB - Springer-Verlag London Ltd CY - Singapore SN - 9789813083868 PY - 1998 SP - 117 EP - 129 PG - 13 UR - https://m2.mtmt.hu/api/publication/1130349 ID - 1130349 LA - English DB - MTMT ER - TY - CHAP AU - Dömösi, Pál Béla AU - Ito, M AU - Katsura, M AU - Nehaniv, C L ED - Bridges, D S ED - [et, al ] TI - A new pumping property of context-free languages T2 - Combinatorics, complexity, and logic : Proceedings of the 1st international conference on discrete mathematics and theoretical computer science, DMTCS ’96 PB - Springer-Verlag London Ltd CY - Berlin SN - 9789813083141 PY - 1997 SP - 187 EP - 193 PG - 7 UR - https://m2.mtmt.hu/api/publication/1130352 ID - 1130352 LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - ITO, Masami TI - On Subwords of Languages JF - SURIKAISEKIKENKYUSHO KOKYUROKU / RIMS KOKYUROKU J2 - RIMS KOKYUROKU VL - 910 PY - 1995 SP - 1 EP - 4 PG - 4 SN - 1880-2818 UR - https://m2.mtmt.hu/api/publication/3323827 ID - 3323827 LA - English DB - MTMT ER - TY - CHAP AU - Dömösi, Pál Béla AU - Horváth, S AU - Ito, M AU - Kászonyi, L AU - Katsura, M ED - Masami, Ito TI - Some combinatorial properties of words, and the Chomsky-hierarchy T2 - Words, languages and combinatorics, II PB - World Scientific Publishing CY - Singapore PY - 1994 SP - 105 EP - 123 PG - 19 UR - https://m2.mtmt.hu/api/publication/1130356 ID - 1130356 LA - English DB - MTMT ER - TY - JOUR AU - Dömösi, Pál Béla AU - Horváth, S AU - Ito, M TI - FORMAL LANGUAGES AND PRIMITIVE WORDS JF - PUBLICATIONES MATHEMATICAE DEBRECEN J2 - PUBL MATH DEBRECEN VL - 42 PY - 1993 IS - 3-4 SP - 315 EP - 321 PG - 7 SN - 0033-3883 UR - https://m2.mtmt.hu/api/publication/1130206 ID - 1130206 AB - The mathematical theory of formal languages has a very important role in theoretical computer science, In this paper we study various formal language problems related to the class of all primitive words over a fixed alphabet. Some results and problems are presented. LA - English DB - MTMT ER - TY - CHAP AU - Dömösi, Pál Béla AU - Horváth, S AU - Ito, M AU - Kászonyi, L AU - Katsura, M ED - Ésik, Zoltán TI - Formal languages consisting of primitive words T2 - Fundamentals of Computation Theory PB - Springer Netherlands CY - Berlin CY - Heidelberg SN - 9783540479239 T3 - Lecture Notes in Computer Science, ISSN 0302-9743 ; 710. PY - 1993 SP - 194 EP - 203 PG - 10 DO - 10.1007/3-540-57163-9_15 UR - https://m2.mtmt.hu/api/publication/1130369 ID - 1130369 LA - English DB - MTMT ER -