{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T08:32:15Z","timestamp":1773390735249,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":7,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540679011","type":"print"},{"value":"9783540446125","type":"electronic"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"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":[[2000]]},"DOI":"10.1007\/3-540-44612-5_13","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:28:20Z","timestamp":1178371700000},"page":"172-181","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Equation Satisfiability and Program Satisfiability for Finite Monoids"],"prefix":"10.1007","author":[{"given":"David Mix","family":"Barrington","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cris","family":"Moore","sequence":"additional","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,6,1]]},"reference":[{"issue":"1","key":"13_CR1","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. A. Barrington","year":"1989","unstructured":"D. A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci., 38(1):150\u2013164, Feb. 1989.","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"13_CR2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0890-5401(90)90007-5","volume":"89","author":"D. A. M. Barrington","year":"1990","unstructured":"D. A. M. Barrington, H. Straubing, and D. Th\u00e9rien. Non-uniform automata over groups. Information and Computation, 89(2):109\u2013132, Dec. 1990.","journal-title":"Information and Computation"},{"key":"13_CR3","unstructured":"S. Eilenberg. Automata, Languages and Machines. Academic Press, 1976."},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"M. Goldmann and A. Russell. The complexity of solving equations over finite groups. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC-99), pages 80\u201386, 1999.","DOI":"10.1109\/CCC.1999.766266"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/BF01212963","volume":"1","author":"P. McKenzie","year":"1991","unstructured":"P. McKenzie, P. P\u00e9ladeau, and D. Th\u00e9rien. NC1: The automata theoretic viewpoint. Computational Complexity, 1:330\u2013359, 1991.","journal-title":"Computational Complexity"},{"key":"13_CR6","unstructured":"P. P\u00e9ladeau and D. Th\u00e9rien. Sur les langages reconnus par des groupes nilpotents. Compte-rendus de l\u2019Acad\u00e9mie des Sciences de Paris, pages 93\u201395, 1988."},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0022-4049(88)90097-7","volume":"52","author":"J.-\u00c9. Pin","year":"1988","unstructured":"J.-\u00c9. Pin, H. Straubing, and D. Th\u00e9rien. Locally trivial categories and unambiguous concatenation. J. Pure Applied Algebra, 52:297\u2013311, 1988.","journal-title":"J. Pure Applied Algebra"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T02:15:30Z","timestamp":1736993730000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":7,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_13","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"1 June 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}