{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:04:33Z","timestamp":1767236673104,"version":"3.40.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00236-012-0157-z","type":"journal-article","created":{"date-parts":[[2012,5,18]],"date-time":"2012-05-18T16:03:20Z","timestamp":1337357000000},"page":"225-248","source":"Crossref","is-referenced-by-count":8,"title":["First-order logics: some characterizations and closure properties"],"prefix":"10.1007","volume":"49","author":[{"given":"Christian","family":"Choffrut","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Malcher","sequence":"additional","affiliation":[]},{"given":"Carlo","family":"Mereghetti","sequence":"additional","affiliation":[]},{"given":"Beatrice","family":"Palano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"157_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai M.: $${\\Sigma_1^1}$$ -Formulae on finite structures. Ann. Pure Appl. Logic 24, 1\u201348 (1983)","journal-title":"Ann. Pure Appl. Logic"},{"key":"157_CR2","first-page":"95","volume":"18","author":"C. Behle","year":"2011","unstructured":"Behle C., Krebs A., Lange K.-J., McKenzie P.: Low uniform versions of NC1. Electron. Colloquium Comput. Complex. (ECCC) 18, 95 (2011)","journal-title":"Electron. Colloquium Comput. Complex. (ECCC)"},{"key":"157_CR3","doi-asserted-by":"crossref","unstructured":"Behle, C., Lange, K.-J.: FO[<]-Uniformity. In: Proceedings of the IEEE Conference Computational Complexity, pp. 183\u2013189 (2006)","DOI":"10.1109\/CCC.2006.20"},{"key":"157_CR4","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J.R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi J.R.: Weak second-order arithmetic and finite automata. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik 6, 66\u201392 (1960)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"157_CR5","doi-asserted-by":"crossref","unstructured":"Chomsky, N., Sch\u00fctzenberger, M.P.: The algebraic theory of context-free languages. In: Braffort, P., Hirschberg, D. (eds.) Computer Programming and Formal Systems, pp. 118\u2013161. North Holland (1963)","DOI":"10.1016\/S0049-237X(08)72023-8"},{"issue":"3","key":"157_CR6","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1006\/jcss.1997.1485","volume":"54","author":"K. Etessami","year":"1997","unstructured":"Etessami K.: Counting quantifiers, successor relations, and logarithmic space. J. Comput. Syst. Sci. 54(3), 400\u2013411 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"157_CR7","unstructured":"Flajolet, P., Steyaert, J.: Complexity of classes of languages and operators. Rap. de Recherche 92, IRIA Laboria (1974)"},{"key":"157_CR8","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"Furst M., Saxe J.B., Sipser M.: Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17, 13\u201327 (1984)","journal-title":"Math. Syst. Theory"},{"key":"157_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"157_CR10","volume-title":"The Mathematical Theory of Context-Free Languages","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York (1966)"},{"key":"157_CR11","first-page":"333","volume":"113","author":"S. Ginsburg","year":"1964","unstructured":"Ginsburg S., Spanier E.H.: Bounded ALGOL-like languages. Trans. Am. Math. Soc. 113, 333\u2013368 (1964)","journal-title":"Trans. Am. Math. Soc."},{"key":"157_CR12","volume-title":"Introduction to formal language theory","author":"M.A. Harrison","year":"1978","unstructured":"Harrison M.A.: Introduction to formal language theory. Addison-Wesley, Reading (1978)"},{"key":"157_CR13","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/S0019-9958(70)80034-1","volume":"17","author":"O. Ibarra","year":"1970","unstructured":"Ibarra O.: Simple matrix languages. Inf Control 17, 359\u2013394 (1970)","journal-title":"Inf Control"},{"key":"157_CR14","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0020-0190(74)90043-X","volume":"3","author":"O. Ibarra","year":"1974","unstructured":"Ibarra O.: A note on semilinear sets and bounded-reversal multihead pushdown automata. Inf. Process. Lett. 3, 25\u201328 (1974)","journal-title":"Inf. Process. Lett."},{"key":"157_CR15","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0020-0190(88)90047-6","volume":"29","author":"O. Ibarra","year":"1988","unstructured":"Ibarra O., Jiang T., Ravikumar B.: Some subclasses of context-free languages in NC1. Inf. Process. Lett. 29, 111\u2013117 (1988)","journal-title":"Inf. Process. Lett."},{"key":"157_CR16","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"Immerman N.: Expressibility and parallel complexity. SIAM J. Comput. 18, 625\u2013638 (1989)","journal-title":"SIAM J. Comput."},{"key":"157_CR17","doi-asserted-by":"crossref","unstructured":"Lange, K.-J.: Some results on majority quantifiers over words. In: IEEE Conference on Computational Complexity, pp. 123\u2013129 (2004)","DOI":"10.1109\/CCC.2004.1313817"},{"key":"157_CR18","doi-asserted-by":"crossref","unstructured":"Lange, K.-J., McKenzie, P.: On the complexity of free monoid morphisms. In: Chwa, K.-Y., Ibarra, O.H (eds.) Proceedings of the ISAAC98, LNCS vol. 1533, pp. 247\u2013256. Springer, New York (1998)","DOI":"10.1007\/3-540-49381-6_27"},{"key":"157_CR19","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1006\/jcss.2000.1742","volume":"62","author":"C. Lautemann","year":"2001","unstructured":"Lautemann C., McKenzie P., Schwentick T., Vollmer H.: The descriptive complexity approach to LOGCFL. J. Comput. Syst. Sci. 62, 629\u2013652 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"157_CR20","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A. Mix Barrington","year":"1989","unstructured":"Mix Barrington D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci. 38, 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"157_CR21","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0020-0190(89)90052-5","volume":"32","author":"D.A. Mix Barrington","year":"1989","unstructured":"Mix Barrington D.A., Corbett J.: On the relative complexity of some languages in NC1. Inf. Process. Lett. 32, 251\u2013256 (1989)","journal-title":"Inf. Process. Lett."},{"key":"157_CR22","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D.A. Mix Barrington","year":"1990","unstructured":"Mix Barrington D.A., Immerman N., Straubing H.: On uniformity within NC1. J. Comput. Syst. Sci. 41, 274\u2013306 (1990)","journal-title":"J. Comput. Syst. Sci."},{"key":"157_CR23","unstructured":"Presburger, M.: \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In: Comptes-Rendus du I Congr\u00e8s de Math\u00e9maticiens des Pays Slaves, pp. 92\u2013101 (1929)"},{"key":"157_CR24","unstructured":"Robinson, D.: Parallel algorithms for group word problems. Doctoral Dissertation, Mathematics Dept., University of California, San Diego (1993)"},{"key":"157_CR25","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1137\/060658035","volume":"37","author":"A. Roy","year":"2007","unstructured":"Roy A., Straubing H.: Definability of languages by generalized first-order formulas over $${\\mathbb{N}^+}$$ . SIAM J. Comput. 37, 502\u2013521 (2007)","journal-title":"SIAM J. Comput."},{"key":"157_CR26","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-1-4615-2696-4_1","volume-title":"Theoretical Advances in Neural Computation and Learning","author":"V. Roychowdhury","year":"1994","unstructured":"Roychowdhury V., Siu K.-Y., Orlitsky A.: Neural models and spectral methods. In: Roychowdhury, V., Siu, K.-Y., Orlitsky, A. (eds.) Theoretical Advances in Neural Computation and Learning, pp. 3\u201336. Kluwer, Amsterdam (1994)"},{"key":"157_CR27","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W.L. Ruzzo","year":"1981","unstructured":"Ruzzo W.L.: On uniform circuit complexity. J. Comput. Syst. Sci. 22, 365\u2013383 (1981)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"157_CR28","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/1071596.1071602","volume":"6","author":"N. Schweikardt","year":"2005","unstructured":"Schweikardt N.: Arithmetic, first-order logic, and counting quantifiers. ACM Trans. Comput. Log. 6(3), 634\u2013671 (2005)","journal-title":"ACM Trans. Comput. Log."},{"key":"157_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite Automata, Formal Logic, and Circuit Complexity","author":"H. Straubing","year":"1994","unstructured":"Straubing H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston (1994)"},{"key":"157_CR30","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/S0022-0000(75)80014-6","volume":"10","author":"I.H. Sudborough","year":"1975","unstructured":"Sudborough I.H.: On tape-bounded complexity classes and multihead finite automata. J. Comput. Syst. Sci. 10, 62\u201376 (1975)","journal-title":"J. Comput. Syst. Sci."},{"key":"157_CR31","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"Wegener I.: The Complexity of Boolean Functions. Teubner, Stuttgart (1987)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-012-0157-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-012-0157-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-012-0157-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T08:31:20Z","timestamp":1743150680000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-012-0157-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["157"],"URL":"https:\/\/doi.org\/10.1007\/s00236-012-0157-z","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2012,5,19]]}}}