{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T17:55:24Z","timestamp":1767894924729,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540194880","type":"print"},{"value":"9783540392910","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-19488-6_142","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:14:43Z","timestamp":1330200883000},"page":"561-575","source":"Crossref","is-referenced-by-count":15,"title":["Regular languages defined with generalized quantifiers"],"prefix":"10.1007","author":[{"given":"Howard","family":"Straubing","sequence":"first","affiliation":[]},{"given":"Denis","family":"Th\u00e9rien","sequence":"additional","affiliation":[]},{"given":"Wolfgang","family":"Thomas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0304-3975(85)90148-3","volume":"39","author":"Arnold","year":"1985","unstructured":"Arnold, A syntactic congreuence for rational \u03c9-languages, Theoretical Computer Science 39, (1985), 333\u2013336.","journal-title":"Theoretical Computer Science"},{"key":"40_CR2","doi-asserted-by":"crossref","unstructured":"D. Barrington, Bounded width polynomial size branching programs recognize exactly those languages in NC 1, Proc. 18th ACM STOC, 1986, 1\u20135.","DOI":"10.1145\/12130.12131"},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"P. Beame, S. Cook and H. Hoover, Log-depth circuits for division and related problems, Proc. 25th IEEE FOCS, 1984, 1\u20136.","DOI":"10.1109\/SFCS.1984.715894"},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"D. Barrington and D. Th\u00e9rien, Finite monoids and the fine structure of NC 1, Proc. 19th ACM STOC, 1987, 101\u2013109.","DOI":"10.1145\/28395.28407"},{"key":"40_CR5","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J. B\u00fcchi","year":"1960","unstructured":"J. B\u00fcchi, Weak second-order arithmetic and finite automata, Z. Math. Logik Grundlagen Math. 6, (1960), 66\u201392.","journal-title":"Z. Math. Logik Grundlagen Math."},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"S. Buss, The boolean formula value problem is in ALOGTIME, Proc. 19th ACM STOC 1987, 123\u2013121.","DOI":"10.1145\/28395.28409"},{"key":"40_CR7","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. Chandra","year":"1984","unstructured":"A. Chandra, L. Stockmeyer and U. Vishkin, Constant-depth reducibility, SIAM J. Computing 13, (1984), 423\u2013439.","journal-title":"SIAM J. Computing"},{"key":"40_CR8","volume-title":"Automata, Languages and Machines","author":"S. Eilenberg","year":"1974","unstructured":"S. Eilenberg, Automata, Languages and Machines, vols. A & B, Academic Press, New York, 1974\u20131976."},{"key":"40_CR9","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1002\/malq.19720181306","volume":"18","author":"G. Fuhrken","year":"1972","unstructured":"G. Fuhrken, A remark on the H\u00e4rtig quantifier, Math. Logik Grundlagen Math. 18, (1972), 227\u2013228.","journal-title":"Math. Logik Grundlagen Math."},{"key":"40_CR10","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"18","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe and M. Sipser, Parity, circuits and the polynomial time hierarchy, J. Math. Systems Theory 18, (1984), 13\u201327.","journal-title":"J. Math. Systems Theory"},{"key":"40_CR11","unstructured":"Y. Gurevich, Logic tailored for complexity, Lecture Notes in Mathematics 1104, Springer, Berlin, 175\u2013216."},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"J. Hastad, Almost optimal lower bounds for small depth circuits, Proc. 18th ACM STOC, 1986, 6\u201320.","DOI":"10.1145\/12130.12132"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"A. Hajnal, W. Maass, P. Pudl\u00e1k, M. Szegedy and G. Tur\u00e1n, Threshold circuits of bounded depth, Proc. 28th IEEE FOCS, 1987.","DOI":"10.1109\/SFCS.1987.59"},{"key":"40_CR14","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0019-9958(77)90443-0","volume":"33","author":"R. Ladner","year":"1977","unstructured":"R. Ladner, Application of model-theoretic games to discrete linear orders and finite automata, Information and Control 33, (1977), 281\u2013303.","journal-title":"Information and Control"},{"key":"40_CR15","volume-title":"Semigroups and Combinatorial Applications","author":"G. Lallement","year":"1979","unstructured":"G. Lallement, Semigroups and Combinatorial Applications, Wiley, New York, 1979."},{"key":"40_CR16","volume-title":"Counter-free Automata","author":"R. McNaughton","year":"1971","unstructured":"R. McNaughton and S. Papert, Counter-free Automata, MIT Press, Cambridge, Mass., 1971."},{"key":"40_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-2215-3","volume-title":"Varieties of Formal Languages","author":"J. E. Pin","year":"1986","unstructured":"J. E. Pin, Varieties of Formal Languages, Plenum, London, 1986."},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"J. Paris and C. Willkie, Counting problems in bounded arithmetic, Lecture Notes in Mathematics 1130, Springer, Berlin, 317\u2013340.","DOI":"10.1007\/BFb0075316"},{"key":"40_CR19","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0022-4049(79)90024-0","volume":"15","author":"H. Straubing","year":"1979","unstructured":"H. Straubing, Families of recognizable sets corresponding to certain varieties of finite monoids, J. Pure and Applied Algebra 15, (1979), 305\u2013318.","journal-title":"J. Pure and Applied Algebra"},{"key":"40_CR20","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for boolean circuit complexity, Proc. 19th ACM STOC, 1987, 77\u201382.","DOI":"10.1145\/28395.28404"},{"key":"40_CR21","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0304-3975(81)90057-8","volume":"14","author":"D. Th\u00e9rien","year":"1981","unstructured":"D. Th\u00e9rien, Classification of finite monoids: the language approach, Theoretical Computer Science 14, (1981), 195\u2013208.","journal-title":"Theoretical Computer Science"},{"key":"40_CR22","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/S0019-9958(79)90629-6","volume":"42","author":"W. Thomas","year":"1979","unstructured":"W. Thomas, Star-free regular sets of \u03c9-sequences, Information and Control 42, (1979), 148\u2013156.","journal-title":"Information and Control"},{"key":"40_CR23","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1016\/0022-0000(82)90016-2","volume":"25","author":"W. Thomas","year":"1982","unstructured":"W. Thomas, Classifying regular events in symbolic logic, J. Computer and Systems Sciences 25, (1982), 360\u2013376.","journal-title":"J. Computer and Systems Sciences"},{"key":"40_CR24","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/S0019-9958(83)80051-5","volume":"56","author":"Wolper","year":"1983","unstructured":"Wolper, Temporal logic can be more expressive, Information and Control 56, (1983), 72\u201379.","journal-title":"Information and Control"},{"key":"40_CR25","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Separating the polynomial-time hierarchy by oracles: Part I, Proc. 26th IEEE FOCS 1985, 1\u201310.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-19488-6_142.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:17:30Z","timestamp":1605644250000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-19488-6_142"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540194880","9783540392910"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-19488-6_142","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988]]}}}