{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:11:31Z","timestamp":1771024291979,"version":"3.50.1"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319049205","type":"print"},{"value":"9783319049212","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-04921-2_2","type":"book-chapter","created":{"date-parts":[[2014,2,5]],"date-time":"2014-02-05T13:52:25Z","timestamp":1391608345000},"page":"14-31","source":"Crossref","is-referenced-by-count":2,"title":["On the Parikh Membership Problem for FAs, PDAs, and CMs"],"prefix":"10.1007","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bala","family":"Ravikumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"2_CR1","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0022-0000(74)80027-9","volume":"8","author":"B.S. Baker","year":"1974","unstructured":"Baker, B.S., Book, R.V.: Reversal-bounded multipushdown machines. J. Comput. Syst. Sci.\u00a08(3), 315\u2013332 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR2","first-page":"23","volume":"30","author":"J. Esparza","year":"1997","unstructured":"Esparza, J.: Petri nets, commutative context-free grammars and basic parallel processes. Fundamenta Informaticae\u00a030, 23\u201341 (1997)","journal-title":"Fundamenta Informaticae"},{"key":"2_CR3","volume-title":"The Mathematical Theory of Context-Free Languages","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York (1966)"},{"key":"2_CR4","unstructured":"Golomb, S.W.: Polyominoes, 2nd edn. Princeton University Press (1994) ISBN 0-691-02444-8"},{"key":"2_CR5","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata, Languages and Computation. Addison-Wesley (1978)"},{"key":"2_CR6","first-page":"291","volume":"6","author":"T.-D. Hyunh","year":"1982","unstructured":"Hyunh, T.-D.: The Complexity of semilinear sets. Elektr. Inform.-verarbeitung and Kybern.\u00a06, 291\u2013338 (1982)","journal-title":"Elektr. Inform.-verarbeitung and Kybern."},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0019-9958(83)80022-9","volume":"57","author":"T.-D. Hyunh","year":"1983","unstructured":"Hyunh, T.-D.: Commutative Grammars: The Complexity of Uniform Word Problems. Information and Control\u00a057, 21\u201339 (1983)","journal-title":"Information and Control"},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"O.H. Ibarra","year":"1978","unstructured":"Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. Assoc. Comput. Mach.\u00a025, 116\u2013133 (1978)","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR9","unstructured":"Ibarra, O.H., Ravikumar, B.: On sparseness and ambiguity for acceptors and transducers. In: Monien, B., Vidal-Naquet, G. (eds.) STACS 1986. LNCS, vol.\u00a0210, pp. 171\u2013179. Springer, Heidelberg (1985)"},{"key":"2_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-642-37064-9_32","volume-title":"Language and Automata Theory and Applications","author":"O.H. Ibarra","year":"2013","unstructured":"Ibarra, O.H., Ravikumar, B.: On bounded languages and reversal-bounded automata. In: Dediu, A.-H., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2013. LNCS, vol.\u00a07810, pp. 359\u2013370. Springer, Heidelberg (2013)"},{"key":"2_CR11","first-page":"1291","volume":"23","author":"O.H. Ibarra","year":"2012","unstructured":"Ibarra, O.H., Seki, S.: Characterizations of bounded semilinear languages by one-way and two-way deterministic machines. IJFCS\u00a023, 1291\u20131306 (2012)","journal-title":"IJFCS"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.tcs.2011.12.034","volume":"429","author":"O.H. Ibarra","year":"2012","unstructured":"Ibarra, O.H., Yen, H.: On the Containment and Equivalence Problems for Two-way Transducers. Theoretical Computer Science\u00a0429, 155\u2013163 (2012)","journal-title":"Theoretical Computer Science"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Kopczynski, E., To, A.W.: Parikh Images of Grammars: Complexity and Applications. In: Proc. of 25th Annual IEEE Logic in Computer Science, pp. 80\u201389 (2010)","DOI":"10.1109\/LICS.2010.21"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-3-642-31653-1_26","volume-title":"Developments in Language Theory","author":"G.J. Lavado","year":"2012","unstructured":"Lavado, G.J., Pighizzini, G., Seki, S.: Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol.\u00a07410, pp. 284\u2013295. Springer, Heidelberg (2012)"},{"key":"2_CR15","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press (2001)"},{"key":"2_CR16","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H.W. Lenstra","year":"1983","unstructured":"Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Mathematics of Operations Research 8, 583\u2013548 (1983)","journal-title":"Mathematics of Operations Research"},{"key":"2_CR17","unstructured":"Lueker, G.S.: Two NP-Complete Problems in Nonnegative Integer Programming. Report No. 178, Computer Science Laboratory, Princeton University (1975)"},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R.J. Parikh","year":"1966","unstructured":"Parikh, R.J.: On context-free languages. J. Assoc. Comput. Mach.\u00a013, 570\u2013581 (1966)","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR19","unstructured":"Scott, D.S.: Programming a combinatorial puzzle. Technical Report No. 1, Department of Electrical Engineering. Princeton University (1958)"},{"key":"2_CR20","unstructured":"To, A.W.: Parikh Images of Regular Languages: Complexity and Applications (2010) (unpublished manuscript)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-04921-2_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T06:00:18Z","timestamp":1558850418000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-04921-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319049205","9783319049212"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-04921-2_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}