{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:07:58Z","timestamp":1773655678490,"version":"3.50.1"},"reference-count":23,"publisher":"Allerton Press","issue":"7","license":[{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Aut. Control Comp. Sci."],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.3103\/s014641161907006x","type":"journal-article","created":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T10:02:40Z","timestamp":1583316160000},"page":"663-675","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Expressive Power of Some Extensions of Linear Temporal Logic"],"prefix":"10.3103","volume":"53","author":[{"given":"A. R.","family":"Gnatenko","sequence":"first","affiliation":[]},{"given":"V. A.","family":"Zakharov","sequence":"additional","affiliation":[]}],"member":"1627","published-online":{"date-parts":[[2020,3,4]]},"reference":[{"key":"7167_CR1","volume-title":"Principles of Model Checking","author":"C. Baier","year":"2008","unstructured":"Baier, C. and Katoen, J., Principles of Model Checking, MIT Press, 2008."},{"key":"7167_CR2","volume-title":"Model Checking","author":"E.M. Clarke","year":"1999","unstructured":"Clarke, E.M., Gramberg, O., and Peled, D.A., Model Checking, MIT Press, 1999."},{"key":"7167_CR3","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1006\/inco.1999.2846","volume":"160","author":"K. Etessami","year":"2000","unstructured":"Etessami, K. and Wilke, T., An until hierarchy and other applications of an Ehrenfeucht-Fraisse game for temporal logic, Inf. Comput., 2000, vol. 160, no. 1, pp. 88\u2013108.","journal-title":"Inf. Comput."},{"key":"7167_CR4","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0022-0000(79)90046-1","volume":"18","author":"J.M. Fisher","year":"1979","unstructured":"Fisher, J.M. and Ladner, R.E., Propositional dynamic logic of regular programs, J. Comput. Syst. Sci., 1979, vol.\u00a018, pp. 194\u2013211.","journal-title":"J. Comput. Syst. Sci."},{"key":"7167_CR5","doi-asserted-by":"crossref","unstructured":"Gabbay, D., Pnueli, A., Shelach, S., and Stavi, J., The temporal analysis of fairness, Proceedings of 7-th ACM Symposium on Principles of Programming Languages, 1980, pp. 163\u2013173.","DOI":"10.1145\/567446.567462"},{"key":"7167_CR6","unstructured":"Gnatenko, A.R. and Zakharov, V.A., On the complexity of verification of finite automata-converters over commutative semigroups, Trudy 18-1 Mezhdunarodnoi konferenii Problemy teoreticheskoi kibernetiki (Proceedings of the 18th International Conference Problems of Theoretical Cybernetics), 2017, pp. 68\u201370."},{"key":"7167_CR7","first-page":"303","volume":"30","author":"A.R. Gnatenko","year":"2018","unstructured":"Gnatenko, A.R. and Zakharov, V.A., On the model checking of finite state transducers over semigroups, Tr. Inst. Sist. Program. Ross. Akad. Nauk, 2018, vol. 30, no. 3, pp. 303\u2013324.","journal-title":"Tr. Inst. Sist. Program. Ross. Akad. Nauk"},{"key":"7167_CR8","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/0022-0000(82)90003-4","volume":"25","author":"D. Harel","year":"1982","unstructured":"Harel, D., Kozen, D., and Parikh, P., Process logic: Expressiveness, decidability, completeness, J. Comput. Syst. Sci., 1982, vol. 25, no. 2, pp. 144\u2013170.","journal-title":"J. Comput. Syst. Sci."},{"key":"7167_CR9","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0168-0072(98)00039-6","volume":"96","author":"J.J. Henriksen","year":"1999","unstructured":"Henriksen, J.J. and Thiagarajan, P.S., Dynamic linear time temporal logic, Ann. Pure Appl. Logic, 1999, vol. 96, nos. 1\u20133, pp. 187\u2013207.","journal-title":"Ann. Pure Appl. Logic"},{"key":"7167_CR10","unstructured":"Kamp, J.A.W., Tense logic and the theory of linear order, PhD Thesis, Los Angeles: University of California, 1968."},{"key":"7167_CR11","first-page":"233","volume":"1698","author":"D.G. Kozlova","year":"2016","unstructured":"Kozlova, D.G. and Zakharov, V.A., On the model checking of sequential reactive systems, Proceedings of the 25th International Workshop on Concurrency, Specification and Programming (CS&P 2016),CEUR Workshop Proceedings, 2016, vol. 1698, pp. 233\u2013244.","journal-title":"CEUR Workshop Proceedings"},{"key":"7167_CR12","doi-asserted-by":"crossref","unstructured":"Kupferman, O., Piterman, N., and Vardi, M.Y., Extended temporal logic revisited, Proceedings of 12-th International Conference on Concurrency Theory, 2001, pp. 519\u2013535.","DOI":"10.1007\/3-540-44685-0_35"},{"key":"7167_CR13","doi-asserted-by":"crossref","unstructured":"Leucker, M. and Sanchez, C., Regular linear temporal logic, Proceedings of the 4-th International Colloquium on Theoretical Aspects of Computing, 2007, pp. 291\u2013305.","DOI":"10.1007\/978-3-540-75292-9_20"},{"key":"7167_CR14","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BFb0025786","volume":"131","author":"Z. Manna","year":"1981","unstructured":"Manna, Z. and Wolper, P., Synthesis of communicating processes from temporal logic specifications, Lect. Notes Comput. Sci., 1981, vol. 131, pp. 253\u2013281.","journal-title":"Lect. Notes Comput. Sci."},{"key":"7167_CR15","series-title":"Automata on infinite objects","volume-title":"Handbook of Theoretical Computer Science","author":"W. Thomas","year":"1990","unstructured":"Thomas, W., Automata on infinite objects, in Handbook of Theoretical Computer Science, vol. B: Formal Models and Semantics, 1990, pp. 133\u2013192."},{"key":"7167_CR16","first-page":"501","volume":"14","author":"M.Y. Vardi","year":"1983","unstructured":"Vardi, M.Y. and Wolper, P., Yet another process logic, Lect. Notes Comput. Sci., 1983, vol. 14, pp. 501\u2013512.","journal-title":"Lect. Notes Comput. Sci."},{"key":"7167_CR17","unstructured":"Vardi, M.Y. and Wolper, P., An automata-theoretic approach to automatic program verification, Proceedings of the First Symposium on Logic in Computer Science, 1986, pp. 322\u2013331."},{"key":"7167_CR18","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y., A temporal fixpoint calculus, Proceedings of the 15-th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1989, pp. 250\u2013259.","DOI":"10.1145\/73560.73582"},{"key":"7167_CR19","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/S0019-9958(83)80051-5","volume":"56","author":"P. Wolper","year":"1983","unstructured":"Wolper, P., Temporal logic can be more expressive, Inf. Control, 1983, vol. 56, nos. 1\u20132, pp. 72\u201399.","journal-title":"Inf. Control"},{"key":"7167_CR20","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BFb0028736","volume":"1427","author":"P. Wolper","year":"1998","unstructured":"Wolper, P. and Boigelot, B., Verifying systems with infinite but regular state spaces, Lect. Notes Comput. Sci., 1998, vol. 1427, pp. 88\u201397.","journal-title":"Lect. Notes Comput. Sci."},{"key":"7167_CR21","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-319-23021-4_19","volume":"9270","author":"V.A. Zakharov","year":"2015","unstructured":"Zakharov, V.A., Equivalence checking problem for finite state transducers over semigroups, Lect. Notes Comput. Sci., 2015, vol. 9270, pp. 208\u2013221.","journal-title":"Lect. Notes Comput. Sci."},{"key":"7167_CR22","doi-asserted-by":"publisher","first-page":"523","DOI":"10.3103\/S0146411617070240","volume":"51","author":"V.A. Zakharov","year":"2017","unstructured":"Zakharov, V.A. and Temerbekova, G.G., On the minimization of finite state transducers over semigroups, Autom. Control Comput. Sci., 2017, vol. 51, no. 7, pp. 523\u2013530.","journal-title":"Autom. Control Comput. Sci."},{"key":"7167_CR23","doi-asserted-by":"publisher","first-page":"689","DOI":"10.3103\/S0146411617070288","volume":"51","author":"V.A. Zakharov","year":"2017","unstructured":"Zakharov, V.A. and Jaylauova S.R., On the minimization problem for sequential programs, Autom. Control Comput. Sci., 2017, vol. 51, no. 7, pp. 689\u2013700.","journal-title":"Autom. Control Comput. Sci."}],"container-title":["Automatic Control and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S014641161907006X.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.3103\/S014641161907006X","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S014641161907006X.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T21:56:26Z","timestamp":1773611786000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.3103\/S014641161907006X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":23,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["7167"],"URL":"https:\/\/doi.org\/10.3103\/s014641161907006x","relation":{},"ISSN":["0146-4116","1558-108X"],"issn-type":[{"value":"0146-4116","type":"print"},{"value":"1558-108X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12]]},"assertion":[{"value":"10 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no conflicts of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"CONFLICT OF INTEREST"}}]}}