{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:12:31Z","timestamp":1767928351401,"version":"3.49.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T00:00:00Z","timestamp":1558569600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N008197\/1"],"award-info":[{"award-number":["EP\/N008197\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["648701"],"award-info":[{"award-number":["648701"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n            We consider the decidability of the membership problem for matrix-exponential semigroups: Given\n            <jats:italic>k<\/jats:italic>\n            \u2208 N and square matrices\n            <jats:italic>A<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026 ,\n            <jats:italic>A<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            ,\n            <jats:italic>C<\/jats:italic>\n            , all of the same dimension and with real algebraic entries, decide whether\n            <jats:italic>C<\/jats:italic>\n            is contained in the semigroup generated by the matrix exponentials exp (\n            <jats:italic>A<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>t<\/jats:italic>\n            ), where\n            <jats:italic>i<\/jats:italic>\n            \u2208 { 1,\u2026 ,\n            <jats:italic>k<\/jats:italic>\n            } and\n            <jats:italic>t<\/jats:italic>\n            \u2265 0. This problem can be seen as a continuous analog of Babai et\u00a0al.\u2019s and Cai et\u00a0al.\u2019s problem of solving multiplicative matrix equations and has applications to reachability analysis of linear hybrid automata and switching systems. Our main results are that the semigroup membership problem is undecidable in general, but decidable if we assume that\n            <jats:italic>A<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026 ,\n            <jats:italic>A<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            commute. The decidability proof is by reduction to a version of integer programming that has transcendental constants. We give a decision procedure for the latter using Baker\u2019s theorem on linear forms in logarithms of algebraic numbers, among other tools. The undecidability result is shown by reduction from Hilbert\u2019s Tenth Problem.\n          <\/jats:p>","DOI":"10.1145\/3286487","type":"journal-article","created":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T16:04:16Z","timestamp":1558713856000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Decidability of Membership in Matrix-exponential Semigroups"],"prefix":"10.1145","volume":"66","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2469-2809","authenticated-orcid":false,"given":"Jo\u00ebl","family":"Ouaknine","sequence":"first","affiliation":[{"name":"Max Planck Institute for Software Systems, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amaury","family":"Pouly","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Software Systems, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jo\u00e3o","family":"Sousa-Pinto","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James","family":"Worrell","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,5,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2774947"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.11.006"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/313852.314109"},{"key":"e_1_2_1_4_1","volume-title":"Transcendental Number Theory","author":"Baker A.","unstructured":"A. Baker . 1975. Transcendental Number Theory . Cambridge University Press . A. Baker. 1975. Transcendental Number Theory. Cambridge University Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196708004925"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.005"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054194000165"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794276853"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.08.004"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2005007"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1965598"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69407-6_28"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"B. Hall. 2015. Lie Groups Lie Algebras and Representations. Springer.  B. Hall. 2015. Lie Groups Lie Algebras and Representations. Springer.","DOI":"10.1007\/978-3-319-13467-3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/788018.788803"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225162"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6496"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009496"},{"key":"e_1_2_1_19_1","unstructured":"S. Lang. 1966. Introduction to Transcendental Number Theory.  S. Lang. 1966. Introduction to Transcendental Number Theory."},{"key":"e_1_2_1_20_1","volume-title":"Kreiseliana: About and Around Georg Kreisel. A K Peters, 441--467.","author":"Macintyre A.","year":"1996","unstructured":"A. Macintyre and A. J. Wilkie . 1996 . On the decidability of the real exponential field. In Kreiseliana: About and Around Georg Kreisel. A K Peters, 441--467. A. Macintyre and A. J. Wilkie. 1996. On the decidability of the real exponential field. In Kreiseliana: About and Around Georg Kreisel. A K Peters, 441--467."},{"key":"e_1_2_1_21_1","volume-title":"New Advances in Transcendence Theory","author":"Masser D. W.","unstructured":"D. W. Masser . 1988. Linear relations on algebraic groups . In New Advances in Transcendence Theory . Cambridge University Press . D. W. Masser. 1988. Linear relations on algebraic groups. In New Advances in Transcendence Theory. Cambridge University Press."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.013"},{"key":"e_1_2_1_23_1","first-page":"105","article-title":"Undecidability in 3\u00d73 matrices","volume":"49","author":"Paterson M. S.","year":"1970","unstructured":"M. S. Paterson . 1970 . Undecidability in 3\u00d73 matrices . Journal of Mathematics and Physics 49 , 1 (1970), 105 -- 107 . M. S. Paterson. 1970. Undecidability in 3\u00d73 matrices. Journal of Mathematics and Physics 49, 1 (1970), 105--107.","journal-title":"Journal of Mathematics and Physics"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039698"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3286487","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3286487","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:44:16Z","timestamp":1750207456000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3286487"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,23]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3286487"],"URL":"https:\/\/doi.org\/10.1145\/3286487","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,23]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}