{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:30:07Z","timestamp":1742956207133,"version":"3.40.3"},"publisher-location":"Wiesbaden","reference-count":22,"publisher":"Vieweg+Teubner Verlag","isbn-type":[{"type":"print","value":"9783815420331"},{"type":"electronic","value":"9783322952332"}],"license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/978-3-322-95233-2_14","type":"book-chapter","created":{"date-parts":[[2013,4,17]],"date-time":"2013-04-17T05:17:04Z","timestamp":1366175824000},"page":"235-251","source":"Crossref","is-referenced-by-count":2,"title":["Complexity of Closeness, Sparseness and Segment Equivalence for Context-Free and Regular Languages"],"prefix":"10.1007","author":[{"given":"Dung T.","family":"Huynh","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"14_CR1","series-title":"SIAM J. of Computing","first-page":"305","volume-title":"On the Isomorphism and Density of NP and other Complete Sets","author":"L Berman","year":"1977","unstructured":"Berman, L. and Hartmanis, J. On the Isomorphism and Density of NP and other Complete Sets. SIAM J. of Computing, pp. 305\u2013322, 1977."},{"key":"14_CR2","unstructured":"Cho, S. and Huynh, D.T. The Parallel Complexity of Finite State Automata Problems, to appear in Information & Computation."},{"key":"14_CR3","first-page":"2","volume":"64","author":"S Cook","year":"1985","unstructured":"Cook, S. A Taxonomy of Problems Which Have Fast Parallel Algorithms. Information & Computation 64, pp. 2\u201322, 1985.","journal-title":"Information & Computation"},{"key":"14_CR4","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, 1966."},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1090\/psapm\/019\/0235938","volume":"19","author":"J Hartmanis","year":"1967","unstructured":"Hartmanis, J. Context-Free Languages and Turing Machine Computations.Proc. Symp. on Applied Mathematics 19, pp. 42\u201351, 1967.","journal-title":"Proc. Symp. on Applied Mathematics"},{"key":"14_CR6","volume-title":"Introduction to Formal Language Theory","author":"MA Harrison","year":"1978","unstructured":"Harrison, M. A. Introduction to Formal Language Theory. Addison-Wesley, 1978."},{"key":"14_CR7","volume-title":"Introduction to Automata Theory, Languages and Computations","author":"J Hopcroft","year":"1979","unstructured":"Hopcroft, J. & Ullman, J. Introduction to Automata Theory, Languages and Computations. Addison-Wesley, 1979."},{"key":"14_CR8","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0304-3975(80)90040-7","volume":"11","author":"G Hotz","year":"1980","unstructured":"Hotz, G. Eine Neue Invariante f\u00fcr Kontext-Freie Sprachen. Theoretical Computer Science 11, pp. 107\u2013116, 1980.","journal-title":"Theoretical Computer Science"},{"key":"14_CR9","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/S0022-0000(76)80038-4","volume":"12","author":"HB Hunt","year":"1976","unstructured":"Hunt, H.B., Rosenkrantz, D.J. and Szymanski, T.G. On the Equivalence, Containment, and Covering Problems for the Regular and Context-Free Languages. J. of Computer and System Science 12, pp. 222\u2013268, 1976.","journal-title":"J. of Computer and System Science"},{"key":"14_CR10","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF00262978","volume":"17","author":"DT Huynh","year":"1982","unstructured":"Huynh, D.T. Remarks on the Complexity of an Invariant of Context-Free Grammars. Acta Informatica 17, pp. 89\u201399, 1982.","journal-title":"Acta Informatica"},{"key":"14_CR11","first-page":"21","volume":"57","author":"DT Huynh","year":"1983","unstructured":"Huynh, D.T. Commutative Grammars: The Complexity of Uniform Word Problems. Information & Computation 57, pp. 21\u201339, 1983.","journal-title":"Information & Computation"},{"key":"14_CR12","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0304-3975(84)90092-6","volume":"33","author":"DT Huynh","year":"1984","unstructured":"Huynh, D.T. Deciding the Inequivalence of Context-Free Grammars with 1-Letter Terminal Alphabet Is \u2211p2\u2014Complete. Theoretical Computer Science 33, pp. 305\u2013326, 1984.","journal-title":"Theoretical Computer Science"},{"key":"14_CR13","first-page":"103","volume":"66","author":"DT Huynh","year":"1985","unstructured":"Huynh, D.T. The Complexity of Equivalence Problems for Commutative Grammars. Information & Computation 66, pp. 103\u2013121, 1985.","journal-title":"Information & Computation"},{"key":"14_CR14","first-page":"1101","volume":"15","author":"DT Huynh","year":"1986","unstructured":"Huynh, D.T. Some Observations about the Randomness of Hard Problems. SIAM J. onComputing 15, pp. 1101\u20131105, 1986.","journal-title":"Computing"},{"key":"14_CR15","series-title":"Proc. 3rd Ann. Symposium on Theoretical Aspects of Computer Science","first-page":"171","volume-title":"On the Sparseness, Ambiguity and Other Decision Problems for Acceptors and Transducers","author":"O Ibarra","year":"1986","unstructured":"Ibarra, O. and Ravikumar, B. On the Sparseness, Ambiguity and Other Decision Problems for Acceptors and Transducers. Proc. 3rd Ann. Symposium on Theoretical Aspects of Computer Science, LNCS 210, pp. 171\u2013179, 1986."},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N Immerman","year":"1988","unstructured":"Immerman, N. Nondeterministic Space Is Closed under Complementation. SIAM J. on Computing. 17, pp. 935\u2013938, 1988.","journal-title":"SIAM J. on Computing"},{"key":"14_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"ND Jones","year":"1976","unstructured":"Jones, N.D., Lien, Y.E. & Laaser, W.T. New Problems Complete for Nondeterministic Log Space. Mathematical Systems Theory 10, pp. 1\u201317, 1976.","journal-title":"Mathematical Systems Theory"},{"key":"14_CR18","series-title":"Proc. 13th IEEE Symp. on Switching and Automata Theory","first-page":"125","volume-title":"The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space","author":"AR Meyer","year":"1972","unstructured":"Meyer, A.R. and Stockmeyer, L.J. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. Proc. 13th IEEE Symp. on Switching and Automata Theory, pp. 125\u2013129, 1972."},{"key":"14_CR19","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF01704904","volume":"19","author":"U Sch\u00f6ning","year":"1986","unstructured":"Sch\u00f6ning, U. Complete Sets and Closeness to Complexity Classes. Mathematical Systems Theory 19, pp. 29\u201341, 1986.","journal-title":"Mathematical Systems Theory"},{"key":"14_CR20","first-page":"1","volume-title":"Word Problem Requiring Exponential Time: Preliminary Report","author":"L Stockmeyer","year":"1973","unstructured":"Stockmeyer, L. & Meyer, A.R. Word Problem Requiring Exponential Time: Preliminary Report. Proc. 5th Ann. ACM Symp. on Theory of Computing, pp. 1\u20139, 1973."},{"key":"14_CR21","first-page":"409","volume-title":"The Complexity of Decision Problems in Automata Theory and Logic","author":"LJ Stockmeyer","year":"1984","unstructured":"Stockmeyer, L.J. The Complexity of Decision Problems in Automata Theory and Logic, Report TR-133, MIT Project MAC, Cambridge, Mass., 1974. by Circuits, SIAM J. on Comput. 13, pp. 409\u2013422, 1984."},{"key":"14_CR22","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0212027","volume":"12","author":"Y Yesha","year":"1983","unstructured":"Yesha, Y. On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets. SIAM J. on Computing 12, pp. 411\u2013425, 1983.","journal-title":"SIAM J. on Computing"}],"container-title":["TEUBNER-TEXTE zur Informatik","Informatik"],"original-title":[],"language":"de","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-322-95233-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,13]],"date-time":"2023-02-13T17:32:03Z","timestamp":1676309523000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-322-95233-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783815420331","9783322952332"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-322-95233-2_14","relation":{},"ISSN":["1615-4584"],"issn-type":[{"type":"print","value":"1615-4584"}],"subject":[],"published":{"date-parts":[[1992]]}}}