{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:32:45Z","timestamp":1725456765338},"publisher-location":"Berlin\/Heidelberg","reference-count":17,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540529535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029607","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T05:33:46Z","timestamp":1133415226000},"page":"187-194","source":"Crossref","is-referenced-by-count":4,"title":["Using inductive counting to simulate nondeterministic computation"],"prefix":"10.1007","author":[{"given":"Gerhard","family":"Buntrock","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lane A.","family":"Hemachandra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk","family":"Siefkes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"16_CR2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"A. Blass and Y. Gurevich. On the unique satisfiability problem. Information and Control, 55:80\u201388, 1982.","journal-title":"Information and Control"},{"key":"16_CR3","series-title":"Technical Report","volume-title":"Using inductive counting to simulate nondeterministic computation","author":"G. Buntrock","year":"1990","unstructured":"G. Buntrock, L. Hemachandra, and D. Siefkes. Using inductive counting to simulate nondeterministic computation. Technical Report 13, Bayerische Julius Maximilians Universit\u00e4t W\u00fcrzburg, W\u00fcrzburg, 1990."},{"key":"16_CR4","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. Inf. and Control, 64:2\u201322, 1985.","journal-title":"Inf. and Control"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"S. Fortune and J. Wyllie. Parallelism in random access machines. In 10th ACM Symposium on Theory of Computing, pages 114\u2013118, 1978.","DOI":"10.1145\/800133.804339"},{"key":"16_CR6","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0304-3975(86)90165-9","volume":"43","author":"L. Goldschlager","year":"1986","unstructured":"L. Goldschlager and I. Parberry. On the construction of parallel computers from various bases of boolean functions. Theoretical Computer Science, 43:43\u201358, 1986.","journal-title":"Theoretical Computer Science"},{"key":"16_CR7","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Commputing, 17:935\u2013938, 1988.","journal-title":"SIAM Journal on Commputing"},{"key":"16_CR8","unstructured":"R. Karp and V. Ramachandra. Parallel algorithms for sharedmemory machines. In The Handbook of Theoretical Computer Science. To appear."},{"key":"16_CR9","unstructured":"K.-J. Lange and P. Rossmanith. Characterizing unambiguous augmented pushdown automata by circuits. These Proceedings."},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proceedings 6th GI Conference on Theoretical Computer Science, pages 269\u2013276. Springer-Verlag, 1983.","DOI":"10.1007\/BFb0009651"},{"issue":"3","key":"16_CR11","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"W. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, 22(3):365\u2013383, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR12","first-page":"75","volume":"73","author":"W. Rytter","year":"1987","unstructured":"W. Rytter. Parallel time O(log N) recognition of unambiguous CFLs. In Information and Control, 73:75\u201386, 1987.","journal-title":"Information and Control"},{"issue":"2","key":"16_CR13","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. Savitch","year":"1970","unstructured":"W. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177\u2013192, 1970.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR14","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. Sudborough","year":"1978","unstructured":"I. Sudborough. On the tape complexity of deterministic contextfree languages. Journal of the ACM, 25:405\u2013414, 1978.","journal-title":"Journal of the ACM"},{"key":"16_CR15","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279\u2013284, 1988.","journal-title":"Acta Informatica"},{"issue":"2","key":"16_CR16","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0020-0190(89)90163-4","volume":"33","author":"A. Szepietowski","year":"1989","unstructured":"A. Szepietowski. Some notes on strong and weak loglogn space complexity. Information Processing Letters, 33(2):109\u2013112, 1989.","journal-title":"Information Processing Letters"},{"key":"16_CR17","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant. The relative complexity of checking and evaluating. Information Processing Letters, 5:20\u201323, 1976.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1990"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T08:15:40Z","timestamp":1586592940000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540529535"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0029607","relation":{},"subject":[]}}