{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:01Z","timestamp":1725490201360},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_47","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"537-547","source":"Crossref","is-referenced-by-count":6,"title":["Satisfiability of Systems of Equations over Finite Monoids"],"prefix":"10.1007","author":[{"given":"Cristopher","family":"Moore","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Tesson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis","family":"Th\u00e9rien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"issue":"4","key":"47_CR1","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. A. M. Barrington","year":"1988","unstructured":"D. A. M. Barrington and D. Th\u00e9rien. Finite monoids and the fine structure of NC 1. Journal of the ACM, 35(4):941\u2013952, Oct. 1988.","journal-title":"Journal of the ACM"},{"key":"47_CR2","doi-asserted-by":"crossref","unstructured":"D. M. Barrington, P. McKenzie, C. Moore, P. Tesson, and D. Th\u00e9rien. Equation satisfiability and program satisfiability for finite monoids. In MFCS\u201900, pages 172\u2013181, 2000.","DOI":"10.1007\/3-540-44612-5_13"},{"key":"47_CR3","unstructured":"V. Dalmau. Computational Complexity of Problems over Generalized Formula. PhD thesis, Universita Polit\u00e9cnica de Catalunya, 2000."},{"key":"47_CR4","unstructured":"S. Eilenberg. Automata, Languages and Machines, volume B. Academic Press, 1976."},{"issue":"1","key":"47_CR5","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing, 28(1):57\u2013104, 1999.","journal-title":"SIAM Journal on Computing"},{"key":"47_CR6","doi-asserted-by":"crossref","unstructured":"M. Goldmann and A. Russell. The complexity of solving equations over finite groups. In Proc. 14th Conf. on Computational Complexity, pages 80\u201386, 1999.","DOI":"10.1109\/CCC.1999.766266"},{"key":"47_CR7","unstructured":"Hertrampf, Lautemann, Schwentick, Vollmer, and Wagner. On the power of polynomial time bit-reductions. In Conf. on Structure in Complexity Theory, 1993."},{"issue":"4","key":"47_CR8","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"P. Jeavons, D. Cohen, and M. Gyssens. Closure properties of constraints. J. ACM, 44(4):527\u2013548, 1997.","journal-title":"J. ACM"},{"key":"47_CR9","unstructured":"O. Klima. Private communication, 2001."},{"key":"47_CR10","unstructured":"J. Pearson and P. Jeavons. A survey of tractable constraint satisfaction problems. Technical Report CSD-TR-97-15, University of London, 1997. Available at http:\/\/www.dcs.rhbnc.ac.uk\/research\/ ."},{"key":"47_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-2215-3","volume-title":"Varieties of formal languages","author":"J.-E. Pin","year":"1986","unstructured":"J.-E. Pin. Varieties of formal languages. North Oxford Academic Publishers Ltd, London, 1986."},{"key":"47_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BFb0055038","volume-title":"An algebraic approach to communication complexity","author":"J.-F. Raymond","year":"1998","unstructured":"J.-F. Raymond, P. Tesson, and D. Th\u00e9rien. An algebraic approach to communication complexity. Lecture Notes in Computer Science, 1443:29\u201340, 1998."},{"key":"47_CR13","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer. The complexity of satisfiability problems. In Proc. 10 th ACM STOC, pages 216\u2013226, 1978.","DOI":"10.1145\/800133.804350"},{"key":"47_CR14","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF02194921","volume":"13","author":"M. P. Sch\u00fctzenberger","year":"1976","unstructured":"M. P. Sch\u00fctzenberger. Sur le produit de concat\u00e9nation non ambigu. Semigroup Forum, 13:47\u201375, 1976.","journal-title":"Semigroup Forum"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T17:27:35Z","timestamp":1556818055000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_47","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}