{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:23Z","timestamp":1759638443214},"reference-count":41,"publisher":"EDP Sciences","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2003,7]]},"DOI":"10.1051\/ita:2003017","type":"journal-article","created":{"date-parts":[[2003,11,14]],"date-time":"2003-11-14T20:25:30Z","timestamp":1068841530000},"page":"179-241","source":"Crossref","is-referenced-by-count":11,"title":["Regular languages definable by Lindstr\u00f6m quantifiers"],"prefix":"10.1051","volume":"37","author":[{"given":"Zolt\u00e1n","family":"\u00c9sik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim G.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2003,11,15]]},"reference":[{"key":"R1","unstructured":"M.A. Arbib (ed.),Algebraic Theory of Machines, Languages, and Semigroups. With a major contribution by K. Krohn and J.L. Rhodes, Academic Press (1968)."},{"key":"R2","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"Barrington","year":"1992","journal-title":"J. Comput. System Sci."},{"key":"R3","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"Barrington","year":"1990","journal-title":"J. Comput. System Sci."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Baziramwabo, P. McKenzie and D. Therien, Modular temporal logic, in:14th Annual IEEE Symposium on Logic in Computer Science, Trento (1999). IEEE Computer Society, 344-351.","DOI":"10.1109\/LICS.1999.782629"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"D. Beauquier and A. Rabinovitch, Monadic logic of order over naturals has no finite base.J. Logic and Comput.(to appear).","DOI":"10.1093\/logcom\/12.2.243"},{"key":"R6","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"B\u00fcchi","year":"1960","journal-title":"Zeit. Math. Logik Grund. Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1142\/S0129054198000180","volume":"9","author":"Burtschick","year":"1998","journal-title":"Int. J. Found. Comput. Sci."},{"key":"R8","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0022-0000(93)90005-H","volume":"46","author":"Cohen","year":"1993","journal-title":"J. Comput. System Sci."},{"key":"R9","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0304-3975(88)90104-1","volume":"61","author":"D\u00f6m\u00f6si","year":"1988","journal-title":"Theoret. Comput. Sci."},{"key":"R10","unstructured":"H.-J. Ebbinghaus and J. Flum,Finite Model Theory. 2nd ed., Springer (1999)."},{"key":"R11","unstructured":"S. Eilenberg,Automata, Languages, and Machines. vol. A and B, Academic Press (1974, 1976)."},{"key":"R12","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","volume":"98","author":"Elgot","year":"1961","journal-title":"Trans. Amer. Math. Soc."},{"key":"R13","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0304-3975(91)90325-V","volume":"87","author":"\u00c9sik","year":"1991","journal-title":"Theoret. Comput. Sci."},{"key":"R14","first-page":"1","volume":"16","author":"\u00c9sik","year":"2003","journal-title":"Acta Cybernet."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"M. Galota and H. Vollmer, A generalization of the B\u00fcchi-Elgot-Trakhtenbrot theorem, in:Computer Science Logic, 15th International Workshop, CSL (2001), Paris (2001), LNCS2142, Springer, 355-368.","DOI":"10.1007\/3-540-44802-0_25"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"N. Immerman,Descriptive Complexity. Graduate Texts in Computer Science, Springer-Verlag, New York (1999).","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"R17","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1090\/S0002-9947-1965-0188316-1","volume":"116","author":"Krohn","year":"1965","journal-title":"Trans. Amer. Math. Soc."},{"key":"R18","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1006\/jcss.2000.1742","volume":"62","author":"Lautemann","year":"2001","journal-title":"J. Comput. System Sci."},{"key":"R19","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","volume":"32","author":"Lindstr\u00f6m","year":"1966","journal-title":"Theoria"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"P. McKenzie, Th. Schwentick, D. Therien and H. Vollmer, The many faces of a translation, in:Automata, Languages and Programming, 27th International Colloquium, ICALP'00, LNCS1853, 890-901.","DOI":"10.1007\/3-540-45022-X_75"},{"key":"R21","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1090\/S0002-9939-1965-0175971-0","volume":"16","author":"Maurer","year":"1965","journal-title":"Proc. Amer. Math. Soc."},{"key":"R22","unstructured":"R. McNaughton and S. Papert,Counter-Free Automata. MIT Press (1971)."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"T. Peichl and H. Vollmer, Finite automata with generalized acceptance criteria, in:Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, LNCS1644, Springer, 605-614.","DOI":"10.1007\/3-540-48523-6_57"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"J.-E. Pin,Varieties of Formal Languages. Plenum (1986).","DOI":"10.1007\/978-1-4613-2215-3"},{"key":"R25","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02127803","volume":"16","author":"Pin","year":"1996","journal-title":"Ann. Math. Artif. Intell."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"A. Pnueli, The temporal logic of programs, in:18th IEEE Symp. Foundations of Computer Science, Providence (1977)46-57.","DOI":"10.1109\/SFCS.1977.32"},{"key":"R27","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1142\/S0218196799000278","volume":"9","author":"Rhodes","year":"1999","journal-title":"Int. J. Algebra and Comput."},{"key":"R28","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0022-4049(89)90137-0","volume":"62","author":"Rhodes","year":"1989","journal-title":"J. Pure Appl. Algebra"},{"key":"R29","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"Sch\u00fctzenberger","year":"1965","journal-title":"Inf. and Control"},{"key":"R30","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0022-4049(79)90024-0","volume":"15","author":"Straubing","year":"1979","journal-title":"J. Pure Appl. Algebra"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"H. Straubing,Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser (1994).","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"H. Straubing, On logical descriptions of regular languages, in:LATIN 2002, LNCS2286, Springer (2002) 528-538.","DOI":"10.1007\/3-540-45995-2_46"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"H. Straubing and D. Therien, Regular languages defined with a bounded number of variables, in:STACS 2001, LNCS2010, Springer (2001) 555-562.","DOI":"10.1007\/3-540-44693-1_48"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"H. Straubing, D. Therien and W. Thomas, Regular languages defined with generalized quantifiers,Automata, languages and programming (Tampere, 1988), Lecture Notes in Comput. Sci.317, Springer, Berlin (1988) 561-575.","DOI":"10.1007\/3-540-19488-6_142"},{"key":"R35","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1006\/inco.1995.1067","volume":"118","author":"Straubing","year":"1995","journal-title":"Inf. and Comput."},{"key":"R36","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0304-3975(81)90057-8","volume":"14","author":"Therien","year":"1981","journal-title":"Theoret. Comput. Sci."},{"key":"R37","doi-asserted-by":"crossref","unstructured":"D. Therien and Th. Wilke, Temporal logic and semidirect products: An effective characterization of the until hierarchy, in:37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington. IEEE Computer Society (1996) 256-263.","DOI":"10.1109\/SFCS.1996.548484"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"W. Thomas, Automata on infinite objects, inHandbook of Theoretical Computer Science. Vol. B, Elsevier, Amsterdam (1990) 133-191.","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"W. Thomas, Languages, automata, and logic, in:Handbook of Formal Languages. Vol. 3, Springer (1997) 389-455.","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"R40","first-page":"326","volume":"140","author":"Trakhtenbrot","year":"1961","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"R41","unstructured":"J. V\u00e4\u00e4n\u00e4nen (ed.),Generalized Quantifiers and Computation, LNCS1754, Springer (1997)."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2003017\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T11:27:05Z","timestamp":1704972425000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2003017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,7]]},"references-count":41,"journal-issue":{"issue":"3"},"alternative-id":["ita0310"],"URL":"https:\/\/doi.org\/10.1051\/ita:2003017","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,7]]}}}