{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:31:55Z","timestamp":1725456715222},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540508403"},{"type":"electronic","value":"9783540460985"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/bfb0029001","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:28:19Z","timestamp":1133396899000},"page":"388-399","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Testing membership: Beyond permutation groups"],"prefix":"10.1007","author":[{"given":"M.","family":"Beaudry","sequence":"first","affiliation":[]},{"given":"P.","family":"McKenzie","sequence":"additional","affiliation":[]},{"given":"D.","family":"Th\u00e9rien","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,16]]},"reference":[{"key":"33_CR1","unstructured":"L. Babai, E. Luks and A. Seress, Permutation Groups in NC, Proc. of the 19th ACM Symp. on the Theory of Computing (1987), pp. 409\u2013420."},{"key":"33_CR2","unstructured":"D. Mix Barrington, N. Immerman and H. Straubing, On uniformity within NC1, Proc. of the 3rd Annual Conf. on the Structure in Complexity Theory, IEEE Computer Society Press (1988), pp. 47\u201359."},{"key":"33_CR3","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1007\/3-540-18088-5_47","volume":"267","author":"M. Beaudry","year":"1987","unstructured":"M. Beaudry, Testing membership in commutative transformation semigroups, Proc. of the 14th International Colloquium on Automata, Languages and Programming, Springer Lecture Notes in Comp. Sci. 267 (1987), pp. 542\u2013549.","journal-title":"Springer Lecture Notes in Comp. Sci."},{"key":"33_CR4","unstructured":"M. Beaudry, Membership Testing in Transformation Monoids, Doctoral Thesis, School of Computer Science, Tech. Rep. TR-SOCS-88.2, McGill University (1988)."},{"key":"33_CR5","unstructured":"S.R. Buss, The boolean formula value problem is in ALOGTIME, Proc. of the 19th ACM Symp. on the Theory of Computing (1987), pp. 123\u2013131."},{"key":"33_CR6","unstructured":"S.A. Cook, The complexity of theorem-proving procedures Proc. of the 3rd ACM Symp. on the Theory of Computing (1971), pp. 151\u2013158."},{"key":"33_CR7","first-page":"2","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"S.A. Cook, A taxonomy of problems with fast parallel solutions, Information and Computation64 (1985), pp. 2\u201322.","journal-title":"Information and Computation"},{"key":"33_CR8","unstructured":"S. Eilenberg, Automata, Languages and Machines, Vol. B, Academic Press (1976)."},{"key":"33_CR9","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/BF02573031","volume":"1","author":"C. Fennemore","year":"1970","unstructured":"C. Fennemore, All varieties of bands, Semigroup Forum1 (1970), pp. 172\u2013177.","journal-title":"Semigroup Forum"},{"key":"33_CR10","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/mana.19710480118","volume":"48","author":"C. Fennemore","year":"1971","unstructured":"C. Fennemore, All varieties of bands I, II, Mathematische Nachrichten48 (1971), pp. 237\u2013252 and 253\u2013262.","journal-title":"Mathematische Nachrichten"},{"key":"33_CR11","unstructured":"M. Furst, J. Hopcroft and E. Luks, Polynomial time algorithms for permutation groups, Proc. of the 21st IEEE Symp. on the Foundations of Computer Science (1980), pp. 36\u201341."},{"key":"33_CR12","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0021-8693(70)90073-6","volume":"15","author":"J.A. Gerhard","year":"1970","unstructured":"J.A. Gerhard, The lattice of equational classes of idempotent semigroups, J. of Algebra15 (1970), pp. 195\u2013224.","journal-title":"J. of Algebra"},{"key":"33_CR13","unstructured":"J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley (1979)."},{"key":"33_CR14","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N.D. Jones","year":"1977","unstructured":"N.D. Jones and W.T. Laaser, Complete problems for deterministic polynomial time, Theoretical Computer Science3 (1977), pp. 105\u2013117.","journal-title":"Theoretical Computer Science"},{"key":"33_CR15","unstructured":"D. Kozen, Lower bounds for natural proof systems, Proc. of the 18th ACM Symp. on the Theory of Computing (1977), pp. 254\u2013266."},{"key":"33_CR16","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1090\/S0002-9947-1965-0188316-1","volume":"116","author":"K. Krohn","year":"1965","unstructured":"K. Krohn and J.L. Rhodes, Algebraic theory of machines, I. Prime decomposition theorem for finite semigroups and machines, Trans. Amer. Math. Soc.116 (1965), pp. 450\u2013464.","journal-title":"Trans. Amer. Math. Soc."},{"key":"33_CR17","unstructured":"G. Lallement, Semigroups and Combinatorial Applications, Addison-Wesley (1979)."},{"key":"33_CR18","unstructured":"E.M. Luks and P. McKenzie, Fast parallel computation with permutation groups, Proc. of the 26th IEEE Symp. on the Foundations of Computer Science (1985), pp. 505\u2013514."},{"key":"33_CR19","unstructured":"E.M. Luks, Parallel algorithms for permutation groups and graph isomorphism, Proc. of the 27th IEEE Symp. on the Foundations of Computer Science (1986), pp. 292\u2013302."},{"key":"33_CR20","unstructured":"P. McKenzie and S.A. Cook, The parallel complexity of the Abelian permutation group membership problem, Proc. of the 24th IEEE Symp. on the Foundations of Computer Science (1983), pp. 154\u2013161."},{"issue":"5","key":"33_CR21","doi-asserted-by":"crossref","first-page":"880","DOI":"10.1137\/0216058","volume":"16","author":"P. McKenzie","year":"1987","unstructured":"P. McKenzie and S.A. Cook, The parallel complexity of Abelian permutation groups problems, SIAM J. on ComputingVol. 16, no. 5 (Oct. 1987), pp. 880\u2013909.","journal-title":"SIAM J. on Computing"},{"key":"33_CR22","unstructured":"J.-E. Pin, Vari\u00e9t\u00e9s de langages formels, Masson (1984)."},{"key":"33_CR23","unstructured":"N. Pippenger, On simultaneous resource bounds, Proc. of the 20th IEEE Symp. on the Foundations of Computer Science (1979), pp. 307\u2013311."},{"key":"33_CR24","unstructured":"C.C. Sims, Computational methods in the study of permutation groups, in Computational Problems in Abstract Algebra, ed. J. Leech, Pergamon Press (1970), pp. 169\u2013183."},{"key":"33_CR25","first-page":"163","volume":"66","author":"J. Stern","year":"1985","unstructured":"J. Stern, Complexity of some problems from the theory of automata, Information and Computation66 (1985), pp. 163\u2013176.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","STACS 89"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029001","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:28:30Z","timestamp":1578526110000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029001"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540508403","9783540460985"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/bfb0029001","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"16 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}