{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:09Z","timestamp":1759638969835},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319080185"},{"type":"electronic","value":"9783319080192"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08019-2_24","type":"book-chapter","created":{"date-parts":[[2014,6,5]],"date-time":"2014-06-05T01:09:47Z","timestamp":1401930587000},"page":"234-244","source":"Crossref","is-referenced-by-count":1,"title":["Predicate Characterizations in the Polynomial-Size Hierarchy"],"prefix":"10.1007","author":[{"given":"Christos A.","family":"Kapoutsis","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01201276","volume":"29","author":"J.-C. Birget","year":"1996","unstructured":"Birget, J.-C.: Two-way automata and length-preserving homomorphisms. Mathematical Systems Theory\u00a029, 191\u2013226 (1996)","journal-title":"Mathematical Systems Theory"},{"key":"24_CR2","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R.M. (ed.) Complexity of Computation. AMS-SIAM Symposia in Applied Mathematics, vol.\u00a0VII, pp. 43\u201373 (1974)"},{"key":"24_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.04.044","volume":"445","author":"V. Geffert","year":"2012","unstructured":"Geffert, V.: An alternating hierarchy for finite automata. Theoretical Computer Science\u00a0445, 1\u201324 (2012)","journal-title":"Theoretical Computer Science"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Descriptive complexity. Springer (1998)","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"24_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/11549345_47","volume-title":"Mathematical Foundations of Computer Science 2005","author":"C. Kapoutsis","year":"2005","unstructured":"Kapoutsis, C.: Removing bidirectionality from nondeterministic finite automata. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 544\u2013555. Springer, Heidelberg (2005)"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-642-02737-6_4","volume-title":"Developments in Language Theory","author":"C. Kapoutsis","year":"2009","unstructured":"Kapoutsis, C.: Size complexity of two-way finite automata. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol.\u00a05583, pp. 47\u201366. Springer, Heidelberg (2009)"},{"key":"24_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-642-31623-4_2","volume-title":"Descriptional Complexity of Formal Systems","author":"C.A. Kapoutsis","year":"2012","unstructured":"Kapoutsis, C.A.: Minicomplexity. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol.\u00a07386, pp. 20\u201342. Springer, Heidelberg (2012)"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-642-31653-1_19","volume-title":"Developments in Language Theory","author":"C. Kapoutsis","year":"2012","unstructured":"Kapoutsis, C., Lefebvre, N.: Analogs of Fagin\u2019s Theorem for small nondeterministic finite automata. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol.\u00a07410, pp. 202\u2013213. Springer, Heidelberg (2012)"},{"key":"24_CR9","unstructured":"Kapoutsis, C., Mulaffer, L.: A descriptive characterization of the power of small 2NFAs (in preparation, 2014)"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: Proceedings of the Symposium on Switching and Automata Theory, pp. 125\u2013129 (1972)","DOI":"10.1109\/SWAT.1972.29"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings of STOC, pp. 275\u2013286 (1978)","DOI":"10.1145\/800133.804357"},{"key":"24_CR12","unstructured":"Sipser, M.: Introduction to the theory of computation, 3rd edn. Cengage Learning (2012)"},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theoretical Computer Science\u00a03, 1\u201322 (1976)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Language, Life, Limits"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08019-2_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T00:37:42Z","timestamp":1558917462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08019-2_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319080185","9783319080192"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08019-2_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}