{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T00:07:09Z","timestamp":1725667629878},"publisher-location":"Wiesbaden","reference-count":14,"publisher":"Vieweg+Teubner Verlag","isbn-type":[{"type":"print","value":"9783519026501"},{"type":"electronic","value":"9783322848239"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/978-3-322-84823-9_16","type":"book-chapter","created":{"date-parts":[[2012,3,10]],"date-time":"2012-03-10T04:25:18Z","timestamp":1331353518000},"page":"169-178","source":"Crossref","is-referenced-by-count":0,"title":["Dot-Depth and Monadic Quantifier Alternation over Pictures \u2014 Extended Abstract"],"prefix":"10.1007","author":[{"given":"Oliver","family":"Matz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, R. Fagin, and L.J. Stockmeyer. The closure of monadic NP. Research Report RJ 10092, IBM, Dec 1997.","DOI":"10.1145\/276698.276771"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai, R. Fagin, and L.J. Stockmeyer. The closure of monadic NP. In The Thirtieth Annual ACM Symposium on Theory of Computing, pages 309\u2013318. SIGACT, 1998.","DOI":"10.1145\/276698.276771"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0022-0000(71)80006-5","volume":"5","author":"JA Brzozowski","year":"1971","unstructured":"J.A. Brzozowski and R. Knast. The dot-depth hierarchy of star-free languages is infinite. Journal of Computer and System Sciences, 5:1\u201316, 1971.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR4","volume-title":"Finite Model Theory","author":"HD Ebbinghaus","year":"1995","unstructured":"H.D. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, New York, 1995."},{"key":"16_CR5","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R.M. Karp, editor, Complexity of Computation, volume 7 of SIAM-Proceedings, pages 43\u201373. AMS, 1974."},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R Fagin","year":"1975","unstructured":"R. Fagin. Monadic generalized spectra. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 21:89\u201396, 1975.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/inco.1995.1100","volume":"120","author":"R Fagin","year":"1995","unstructured":"R. Fagin, L.J. Stockmeyer, and M.Y. Vardi. On monadic NP vs. monadic co-NP. Information and Computation, 120:78\u201392, 1995.","journal-title":"Information and Computation"},{"key":"16_CR8","first-page":"125","volume-title":"Handbook of Formal Language Theory","author":"D Giammarresi","year":"1996","unstructured":"D. Giammarresi and A. Restivo. Two-dimensional languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Language Theory, volume III, pages 125\u2013267. Springer-Verlag, New York, 1996."},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"O. Matz. On piecewise testable, starfree, and recognizable picture languages. In Maurice Nivat, editor, Foundations of Software Science and Computation Structures, volume 1378 of Lecture Notes in Computer Science, pages 203\u2013210. Springer, 1998.","DOI":"10.1007\/BFb0053551"},{"key":"16_CR10","unstructured":"O. Matz. Dot-depth and monadic quantifier alternation over pictures. Aachener Informatik-Berichte 99\u201308, RWTH Aachen, Ahornstr. 55, D-52074 Aachen, 1999."},{"issue":"1\u20133","key":"16_CR11","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0168-0072(95)00013-5","volume":"78","author":"JA Makowsky","year":"1996","unstructured":"J.A. Makowsky and Y.B. Pnueli. Arity and alternation in second-order logic. Annals of Pure and Applied Logic, 78(1\u20133):189\u2013202, 1996.","journal-title":"Annals of Pure and Applied Logic"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1109\/LICS.1997.614951","volume-title":"Twelfth Annual IEEE Symposium on Logic in Computer Science","author":"O Matz","year":"1997","unstructured":"O. Matz and W. Thomas. The monadic quantifier alternation hierarchy over graphs is infinite. In Twelfth Annual IEEE Symposium on Logic in Computer Science, pages 236\u2013244, Warsaw, Poland, 1997. IEEE."},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"N. Schweikardt. The monadic quantifier alternation hierarchy over grids and pictures. In Mogens Nielson and Wolfgang Thomas, editors, Computer Science Logic, volume 1414 of Lecture Notes in Computer Science, pages 441\u2013460. Springer, 1997.","DOI":"10.1007\/BFb0028030"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/3-540-63165-8_191","volume-title":"Automata, Languages and Programming","author":"Th Wilke","year":"1997","unstructured":"Th. Wilke. Star-free picture expressions are strictly weaker than first-order logic. In Pierpaolo Degano, Roberto Gorrieri, and Alberto Marchetti-Spaccamela, editors, Automata, Languages and Programming, volume 1256, pages 347\u2013357. Springer, Bologna, Italy, 1997."}],"container-title":["Ausgezeichnete Informatikdissertationen 1999"],"original-title":[],"language":"de","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-322-84823-9_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,2]],"date-time":"2021-05-02T13:41:02Z","timestamp":1619962862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-322-84823-9_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783519026501","9783322848239"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-322-84823-9_16","relation":{},"subject":[],"published":{"date-parts":[[2000]]}}}