{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:20:59Z","timestamp":1725456059938},"publisher-location":"Berlin\/Heidelberg","reference-count":18,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354055789X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0023758","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T05:11:10Z","timestamp":1132377070000},"page":"68-78","source":"Crossref","is-referenced-by-count":0,"title":["How to implement first order formulas in local memory machine models"],"prefix":"10.1007","author":[{"given":"Elias","family":"Dahlhaus","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","unstructured":"F. Abolhassan, J. Keller, W. Paul: On physical realizations of the theoretical PRAM model, Technical Report # 21\/90, Sonderforschungsbereich 124 \u2014 VLSI-Entwurfsmethoden und Parallelit\u00e4t, University of Saarbr\u00fccken."},{"key":"5_CR2","volume-title":"The design and analysis of parallel algorithms","author":"S. Akl","year":"1989","unstructured":", S. Akl: The design and analysis of parallel algorithms, Prentice Hall, Englewood Cliffs, New Jersey, 1989"},{"key":"5_CR3","unstructured":"B. Awerbuch, A. Israeli, Y. Shiloach: Efficient simulation of PRAM by ultracomputer, preprint, Technion-Israel Institute of Technology, 1983."},{"key":"5_CR4","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1109\/TC.1987.1676869","volume":"C-36","author":"B. Awerbuch","year":"1987","unstructured":"B. Awerbuch, Y. Shiloach: New connectivity and MSF algorithms for shuffle exchange network and PRAM, IEEE-Transactions on Computing C-36 (1987), pp. 1258\u20131263.","journal-title":"IEEE-Transactions on Computing"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"K. Batcher: Sorting networks and their applications, Proceedings of the AFIPS 1968, Atlanta City, New jersey, pp. 307\u2013314.","DOI":"10.1145\/1468075.1468121"},{"key":"5_CR6","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1145\/358628.358650","volume":"25","author":"Y. Chin","year":"1982","unstructured":"Y. Chin, Y. Lam, I. Chen: Efficient parallel algorithms for some graph problems, Communication of the ACM 25 (1982), pp. 659\u2013665.","journal-title":"Communication of the ACM"},{"key":"5_CR7","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. Cook","year":"1985","unstructured":"S. Cook: A taxonomy of problems with fast parallel algorithms, Information and Control 64 (1985), pp. 2\u201322.","journal-title":"Information and Control"},{"key":"5_CR8","unstructured":"R. Cypher, G. Plaxton: Deterministic sorting in nearly logarithmic time on a hypercube and related computers, 2n d ACM-STOC (1990), pp. 193\u2013203."},{"key":"5_CR9","unstructured":"R. Fagin: Generalized first order spectra and polynomial time recognizable sets, in \u201dComplexity of Computations\u201d (R. Karp ed.), SIAM-AMS-proceedings 7 (1974), pp.27\u201341."},{"key":"5_CR10","unstructured":"S. Fortune, J. Wyllie: Parallelism in random access machines, 10th ACM-STOC (1978), pp. 114\u2013118."},{"key":"5_CR11","volume-title":"Efficient Parallel Algorithms","author":"A. Gibbons","year":"1989","unstructured":"A. Gibbons, W. Rytter: Efficient Parallel Algorithms, Cambridge University Press, Cambridge, 1989."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"N. Immerman: Languages which capture complexity classes, 15th ACM-STOC (1983) pp. 347\u2013354.","DOI":"10.1145\/800061.808765"},{"key":"5_CR13","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"N. Immerman: Expressibility and parallel complexity, SIAM-Journal on Computing 18 (1989), pp. 625\u2013638.","journal-title":"SIAM-Journal on Computing"},{"key":"5_CR14","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/2272354","volume":"39","author":"N. Jones","year":"1974","unstructured":"N. Jones, A. Selman: Turing machines and spectra of first order formulas, Journal of Symbolic Logic 39 (1974), pp. 139\u2013150.","journal-title":"Journal of Symbolic Logic"},{"key":"5_CR15","unstructured":"R. Miller, Q. Stout: Graph and image processing algorithms for hypercube, Proceedings 1986 SIAM Conference on Hypercube Multiprocessors (1987), pp. 418\u2013425."},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"A. Ranade: How to emulate shared memory, IEEE-FOCS 1987, pp.185\u2013194.","DOI":"10.1109\/SFCS.1987.32"},{"key":"5_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/malq.19720180102","volume":"18","author":"D. R\u00f6dding","year":"1972","unstructured":"D. R\u00f6dding, H. Schwichtenberg: Bemerkungen zum Spektralproblem, Zeitschrift f\u00fcr Mathematische Logik 18 (1972), pp. 1\u201312.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"E. Upfal: An O(log N) deterministic packet routing scheme, 21st ACM-STOC (1989), pp. 241\u2013250.","DOI":"10.1145\/73007.73030"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0023758.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:50:27Z","timestamp":1607532627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0023758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354055789X"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/bfb0023758","relation":{},"subject":[]}}