{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:45:44Z","timestamp":1725493544597},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_48","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T02:29:04Z","timestamp":1193538544000},"page":"579-590","source":"Crossref","is-referenced-by-count":3,"title":["Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages"],"prefix":"10.1007","author":[{"given":"Tero","family":"Harju","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oscar","family":"Ibarra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juhani","family":"Karhum\u00e4ki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arto","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"48_CR1","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1142\/S0129054196000191","volume":"7","author":"L. Breveglieri","year":"1996","unstructured":"L. Breveglieri, A. Cherubini, C. Citrini, and S. Crespi Reghizzi. Multiple pushdown languages and grammars. Internat. J. Found. Comput. Sci. 7 (1996), 253\u2013291.","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"48_CR2","doi-asserted-by":"crossref","unstructured":"C. Choffrut and J. Karhum\u00e4ki, Combinatorics of words, in Handbook of Formal Languages, Vol. 1, (A. Salomaa and G. Rozenberg, eds.), Springer-Verlag, 1997, pp. 329\u2013438.","DOI":"10.1007\/978-3-642-59136-5_6"},{"key":"48_CR3","unstructured":"C. Choffrut and J. Karhum\u00e4ki. Characterizing the subsets of words commuting with a set of two words. Proc. 7th Nordic Combinatorial Conference, Turku, Finland, 1999."},{"key":"#cr-split#-48_CR4.1","unstructured":"C. Choffrut, J. Karhum??ki, and N. Ollinger. The commutation of finite sets: challenging problem. Theoret. Comput. Sci., to appear;"},{"key":"#cr-split#-48_CR4.2","unstructured":"TUCS Technical Report 303, http:\/\/www.tucs.fi, 1999."},{"key":"48_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0022-0000(78)90002-8","volume":"17","author":"K. Culik II","year":"1978","unstructured":"K. Culik II and A. Salomaa. On the decidability of homomorphism equivalence for languages. J. Comput. System Sci. 17, (1978), 163\u2013175.","journal-title":"J. Comput. System Sci."},{"key":"48_CR6","unstructured":"Z. Dang. Verification and Debugging of Infinite State Real-time Systems. Ph.D. Thesis, University of California, Santa Barbara, 2000."},{"key":"48_CR7","volume-title":"The Mathematical Theory of Context-Free Languages","author":"S. Ginsburg","year":"1966","unstructured":"S. Ginsburg. The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York, 1966."},{"key":"48_CR8","doi-asserted-by":"crossref","unstructured":"S. A. Greibach. Checking automata and one-way stack languages. SDC Document TM 738\/045\/00, 1968.","DOI":"10.1109\/SWAT.1968.6"},{"key":"48_CR9","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(81)90028-3","volume":"22","author":"E. M. Gurari","year":"1981","unstructured":"E. M. Gurari and O. H. Ibarra. The complexity of decision problems for finite-turn multicounter machines. J. Comput. System Sci. 22 (1981), 220\u2013229.","journal-title":"J. Comput. System Sci."},{"key":"48_CR10","first-page":"189","volume":"38","author":"V. Halava","year":"1999","unstructured":"V. Halava and T. Harju. Undecidability in integer weighted finite automata. Fund. Inf. 38 (1999), 189\u2013200.","journal-title":"Fund. Inf."},{"key":"48_CR11","volume-title":"Introduction to Formal Language Theory","author":"M. Harrison","year":"1978","unstructured":"M. Harrison. Introduction to Formal Language Theory. Addison-Wesley, Reading, Mass., 1978."},{"key":"48_CR12","first-page":"441","volume":"23","author":"S. Horvath","year":"1987","unstructured":"S. Horvath, J. Karhum\u00e4 and H. C. M. Kleijn. Results concerning palindromicity. J. Int. Process. Cyber. EIK 23 (1987), 441\u2013451.","journal-title":"J. Int. Process. Cyber. EIK"},{"key":"48_CR13","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"O. H. Ibarra","year":"1978","unstructured":"O. H. Ibarra. Reversal-bounded multicounter machines and their decision problems. J. ACM 25 (1978), 116\u2013133.","journal-title":"J. ACM"},{"key":"48_CR14","doi-asserted-by":"crossref","unstructured":"O. H. Ibarra, T. Bultan, and J. Su. Reachability analysis for some models of infinite-state transition systems. Proc. 10th Int. Conf. on Concurrency Theory, 2000.","DOI":"10.1007\/3-540-44618-4_15"},{"key":"48_CR15","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1137\/S0097539792240625","volume":"24","author":"O. H. Ibarra","year":"1995","unstructured":"O. H. Ibarra, T. Jiang, N. Tran, and H. Wang. New decidability results concerning two-way counter machines. SIAM J. Comput. 24 (1995), 123\u2013137.","journal-title":"SIAM J. Comput."},{"key":"48_CR16","doi-asserted-by":"crossref","unstructured":"J. Karhum\u00e4ki and L. P. Lisovik. A simple undecidable problem: the inclusion problem for finite substitutions on ab * c. Proc. of the STACS 2001, to appear.","DOI":"10.1007\/3-540-44693-1_34"},{"key":"48_CR17","unstructured":"M. Lothaire, Combinatorics on Words, Addison-Wesley, 1983."},{"key":"48_CR18","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R. Parikh","year":"1966","unstructured":"R. Parikh. On context-free languages. J. ACM 13 (1966), 570\u2013581.","journal-title":"J. ACM"},{"key":"48_CR19","volume-title":"Formal Languages","author":"A. Salomaa","year":"1973","unstructured":"A. Salomaa. Formal Languages. Academic Press, New York, 1973."},{"key":"48_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00285-1","volume":"251","author":"G. S\u00e9nizergues","year":"2001","unstructured":"G. S\u00e9nizergues. L(A)=L(B)? decidability results from complete formal systems. Theoret. Comput. Sci. 251 (2001), 1\u2013166.","journal-title":"Theoret. Comput. Sci."},{"key":"48_CR21","unstructured":"C. Stirling. Decidability of DPDA equivalence. Theoret. Comput. Sci., to appear."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T22:28:15Z","timestamp":1556922495000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_48","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}