{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T07:19:42Z","timestamp":1773818382895,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T00:00:00Z","timestamp":1681084800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T00:00:00Z","timestamp":1681084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2023,9]]},"abstract":"Abstract<\/jats:title>In Freydenberger (Theory Comput Syst 53(2):159\u2013193, 2013. https:\/\/doi.org\/10.1007\/s00224-012-9389-0<\/jats:ext-link>), Freydenberger shows that the set of invalid computations of an extended Turing machine can be recognized by a synchronized regular expression [as defined in Della Penna et al. (Acta Informatica 39(1):31\u201370, 2003. https:\/\/doi.org\/10.1007\/s00236-002-0099-y<\/jats:ext-link>)]. Therefore, the widely discussed predicate \u201c$$=\\{0,1\\}^*$$<\/jats:tex-math>\n \n =<\/mml:mo>\n \n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n \u2217<\/mml:mo>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u201d is not recursively enumerable for synchronized regular expressions (SRE). In this paper, we employ a stronger form of non-recursive enumerability called productiveness<\/jats:italic> and show that the set of invalid computations of a deterministic Turing machine on a single input can be recognized by a synchronized regular expression. Hence, for a polynomial-time decidable subset of SRE, where each expression generates either $$\\{0, 1\\}^*$$<\/jats:tex-math>\n \n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n \u2217<\/mml:mo>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or $$\\{0, 1\\}^* -\\{w\\}$$<\/jats:tex-math>\n \n \n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n \u2217<\/mml:mo>\n <\/mml:msup>\n -<\/mml:mo>\n \n {<\/mml:mo>\n w<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> where $$w \\in \\{0, 1\\}^*$$<\/jats:tex-math>\n \n w<\/mml:mi>\n \u2208<\/mml:mo>\n \n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n \u2217<\/mml:mo>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the predicate \u201c$$=\\{0,1\\}^*$$<\/jats:tex-math>\n \n =<\/mml:mo>\n \n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n \u2217<\/mml:mo>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u201d is productive. This result can be easily applied to other classes of language descriptors due to the simplicity of the construction in its proof. This result also implies that many computational problems, especially promise problems, for SRE are productive. These problems include language class comparison problems (e.g., does a given synchronized regular expression generate a context-free language?), and equivalence and containment problems of several types (e.g., does a given synchronized regular expression generate a language equal to a fixed unbounded regular set?). In addition, we study the descriptional complexity of SRE. A generalized method for studying trade-offs between SRE and many classes of language descriptors is established.<\/jats:p>","DOI":"10.1007\/s00236-023-00439-3","type":"journal-article","created":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T14:02:56Z","timestamp":1681135376000},"page":"257-278","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["On the undecidability and descriptional complexity of synchronized regular expressions"],"prefix":"10.1007","volume":"60","author":[{"given":"Jingnan","family":"Xie","sequence":"first","affiliation":[]},{"suffix":"III","given":"Harry B.","family":"Hunt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,10]]},"reference":[{"key":"439_CR1","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/B978-0-444-88071-0.50010-2","volume-title":"Handbook of Theoretical Computer Science Vol A: Algorithms and Complexity","author":"AV Aho","year":"1990","unstructured":"Aho, A.V.: Algorithms for finding patterns in strings. In: Van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science Vol A: Algorithms and Complexity, pp. 255\u2013300. Elsevier, Amsterdam (1990). https:\/\/doi.org\/10.1016\/B978-0-444-88071-0.50010-2"},{"key":"439_CR2","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2022.10.041","volume":"940","author":"M Berglund","year":"2023","unstructured":"Berglund, M., Van der Merwe, B.: Re-examining regular expressions with backreferences. Theoret. Comput. Sci. 940, 66\u201380 (2023). https:\/\/doi.org\/10.1016\/j.tcs.2022.10.041","journal-title":"Theoret. Comput. Sci."},{"issue":"24","key":"439_CR3","doi-asserted-by":"publisher","first-page":"2336","DOI":"10.1016\/j.tcs.2009.02.022","volume":"410","author":"C C\u00e2mpeanu","year":"2009","unstructured":"C\u00e2mpeanu, C., Santean, N.: On the intersection of regex languages with regular languages. Theor. Comput. Sci. 410(24), 2336\u20132344 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.02.022","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"439_CR4","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1142\/S012905410300214X","volume":"14","author":"C C\u00e2mpeanu","year":"2003","unstructured":"C\u00e2mpeanu, C., Salomaa, K., Yu, S.: A formal study of practical regular expressions. Int. J. Found. Comput. Sci. 14(6), 1007\u20131018 (2003). https:\/\/doi.org\/10.1142\/S012905410300214X","journal-title":"Int. J. Found. Comput. Sci."},{"key":"439_CR5","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-642-00982-2_24","volume-title":"Language and Automata Theory and Applications. LATA 2009. Lecture Notes in Computer Science","author":"B Carle","year":"2009","unstructured":"Carle, B., Narendran, P.: On extended regular expressions. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) Language and Automata Theory and Applications. LATA 2009. Lecture Notes in Computer Science, vol. 5457, pp. 279\u2013289. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-642-00982-2_24"},{"issue":"1","key":"439_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00236-002-0099-y","volume":"39","author":"G Della Penna","year":"2003","unstructured":"Della Penna, G., Intrigila, B., Tronci, E., Venturini Zilli, M.: Synchronized regular expressions. Acta Informatica 39(1), 31\u201370 (2003). https:\/\/doi.org\/10.1007\/s00236-002-0099-y","journal-title":"Acta Informatica"},{"issue":"2","key":"439_CR7","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00224-012-9389-0","volume":"53","author":"DD Freydenberger","year":"2013","unstructured":"Freydenberger, D.D.: Extended regular expressions: succinctness and decidability. Theory Comput. Syst. 53(2), 159\u2013193 (2013). https:\/\/doi.org\/10.1007\/s00224-012-9389-0","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"439_CR8","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.ic.2009.04.002","volume":"208","author":"DD Freydenberger","year":"2010","unstructured":"Freydenberger, D.D., Reidenbach, D.: Bad news on decision problems for patterns. Inf. Comput. 208(1), 83\u201396 (2010). https:\/\/doi.org\/10.1016\/j.ic.2009.04.002","journal-title":"Inf. Comput."},{"key":"439_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2019.04.001","volume":"105","author":"DD Freydenberger","year":"2019","unstructured":"Freydenberger, D.D., Schmid, M.L.: Deterministic regular expressions with back-references. J. Comput. Syst. Sci. 105, 1\u201339 (2019). https:\/\/doi.org\/10.1016\/j.jcss.2019.04.001","journal-title":"J. Comput. Syst. Sci."},{"key":"439_CR10","doi-asserted-by":"publisher","unstructured":"Ginsburg, S., Greibach, S.: Abstract families of languages. In: Studies in Abstract Families of Languages, pp. 1\u201332. Memoirs of the American Mathematical Society, Providence (1969). https:\/\/doi.org\/10.1090\/memo\/0087","DOI":"10.1090\/memo\/0087"},{"key":"439_CR11","unstructured":"Hartmanis, J., Stearns, R.E.: Algebraic Structure Theory of Sequential Machines (Prentice-Hall International Series in Applied Mathematics). Prentice-Hall Inc (1966)"},{"issue":"4","key":"439_CR12","doi-asserted-by":"publisher","first-page":"759","DOI":"10.2307\/2272443","volume":"37","author":"J Hartmanis","year":"1972","unstructured":"Hartmanis, J.: Context-free languages and Turing machine computations. J. Symb. Logic 37(4), 759 (1972). https:\/\/doi.org\/10.2307\/2272443","journal-title":"J. Symb. Logic"},{"key":"439_CR13","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/3-540-09510-1_22","volume-title":"Automata, Languages and Programming: Sixth Colloquium. ICALP 1979. Lecture Notes in Computer Science","author":"J Hartmanis","year":"1979","unstructured":"Hartmanis, J.: On the succinctness of different representations of languages. In: Maurer, H.A. (ed.) Automata, Languages and Programming: Sixth Colloquium. ICALP 1979. Lecture Notes in Computer Science, vol. 71, pp. 282\u2013288. Springer, Berlin, Heidelberg (1979). https:\/\/doi.org\/10.1007\/3-540-09510-1_22"},{"key":"439_CR14","doi-asserted-by":"publisher","unstructured":"Holzer, M., Kutrib, M.: Descriptional complexity\u2014an introductory survey. In: Mart\u00edn-Vide, C. (ed.) Scientific Applications of Language Methods. Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory, vol. 2, pp. 1\u201358. World Scientific, Singapore (2010). https:\/\/doi.org\/10.1142\/9781848165458_0001","DOI":"10.1142\/9781848165458_0001"},{"key":"439_CR15","volume-title":"Formal Languages and Their Relation to Automata","author":"JE Hopcroft","year":"1969","unstructured":"Hopcroft, J.E., Ullman, J.D.: Formal Languages and Their Relation to Automata. Addison-Wesley Longman Publishing Co. Inc., Boston (1969)"},{"key":"439_CR16","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"issue":"3","key":"439_CR17","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1145\/322017.322020","volume":"24","author":"HB Hunt III","year":"1977","unstructured":"Hunt, H.B., III., Rosenkrantz, D.J.: On equivalence and containment problems for formal languages. J. ACM 24(3), 387\u2013396 (1977). https:\/\/doi.org\/10.1145\/322017.322020","journal-title":"J. ACM"},{"issue":"1","key":"439_CR18","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/0207007","volume":"7","author":"HB Hunt III","year":"1978","unstructured":"Hunt, H.B., III., Rosenkrantz, D.J.: Computational parallels between the regular and context-free languages. SIAM J. Comput. 7(1), 99\u2013114 (1978). https:\/\/doi.org\/10.1137\/0207007","journal-title":"SIAM J. Comput."},{"issue":"1","key":"439_CR19","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0304-3975(94)00087-Y","volume":"141","author":"L Kari","year":"1995","unstructured":"Kari, L., Mateescu, A., P\u01ceun, G., Salomaa, A.: Multi-pattern languages. Theoret. Comput. Sci. 141(1), 253\u2013268 (1995). https:\/\/doi.org\/10.1016\/0304-3975(94)00087-Y","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"439_CR20","doi-asserted-by":"publisher","first-page":"549","DOI":"10.25596\/jalc-2002-549","volume":"7","author":"A Malcher","year":"2002","unstructured":"Malcher, A.: Descriptional complexity of cellular automata and decidability questions. J. Autom. Lang. Comb. 7(4), 549\u2013560 (2002). https:\/\/doi.org\/10.25596\/jalc-2002-549","journal-title":"J. Autom. Lang. Comb."},{"issue":"1","key":"439_CR21","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0019-9958(67)90481-0","volume":"11","author":"R McNaughton","year":"1967","unstructured":"McNaughton, R.: The loop complexity of pure-group events. Inf. Control 11(1), 167\u2013176 (1967). https:\/\/doi.org\/10.1016\/S0019-9958(67)90481-0","journal-title":"Inf. Control"},{"key":"439_CR22","volume-title":"Counter-Free Automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press, Cambridge (1971)"},{"issue":"3","key":"439_CR23","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1145\/321281.321292","volume":"12","author":"A Paz","year":"1965","unstructured":"Paz, A., Peleg, B.: Ultimate-definite and symmetric-definite events and automata. J. ACM 12(3), 399\u2013410 (1965). https:\/\/doi.org\/10.1145\/321281.321292","journal-title":"J. ACM"},{"issue":"3","key":"439_CR24","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1109\/TC.1968.229096","volume":"C\u201317","author":"A Paz","year":"1968","unstructured":"Paz, A., Peleg, B.: On concatenative decompositions of regular events. IEEE Trans. Comput. C\u201317(3), 229\u2013237 (1968). https:\/\/doi.org\/10.1109\/TC.1968.229096","journal-title":"IEEE Trans. Comput."},{"key":"439_CR25","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H Rogers Jr","year":"1987","unstructured":"Rogers, H., Jr.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987)"},{"issue":"07","key":"439_CR26","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1142\/S0129054113400340","volume":"24","author":"ML Schmid","year":"2013","unstructured":"Schmid, M.L.: Inside the class of regex languages. Int. J. Found. Comput. Sci. 24(07), 1117\u20131134 (2013). https:\/\/doi.org\/10.1142\/S0129054113400340","journal-title":"Int. J. Found. Comput. Sci."},{"key":"439_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2016.02.003","volume":"249","author":"ML Schmid","year":"2016","unstructured":"Schmid, M.L.: Characterising regex languages by regular languages equipped with factor-referencing. Inf. Comput. 249, 1\u201317 (2016). https:\/\/doi.org\/10.1016\/j.ic.2016.02.003","journal-title":"Inf. Comput."},{"key":"439_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7","volume-title":"Recursively Enumerable Sets and Degrees","author":"RI Soare","year":"1987","unstructured":"Soare, R.I.: Recursively Enumerable Sets and Degrees. Springer, Berlin (1987)"},{"key":"439_CR29","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF01691347","volume":"2","author":"G Thierrin","year":"1968","unstructured":"Thierrin, G.: Permutation automata. Math. Syst. Theory 2, 83\u201390 (1968). https:\/\/doi.org\/10.1007\/BF01691347","journal-title":"Math. Syst. Theory"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-023-00439-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-023-00439-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-023-00439-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T09:02:29Z","timestamp":1691658149000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-023-00439-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,10]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["439"],"URL":"https:\/\/doi.org\/10.1007\/s00236-023-00439-3","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,10]]},"assertion":[{"value":"13 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}