{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T00:27:27Z","timestamp":1777508847769,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540558088","type":"print"},{"value":"9783540472919","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55808-x_48","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T09:46:59Z","timestamp":1330249619000},"page":"494-503","source":"Crossref","is-referenced-by-count":37,"title":["Characterizing regular languages with polynomial densities"],"prefix":"10.1007","author":[{"given":"Andrew","family":"Szilard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sheng","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kaizhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey","family":"Shallit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"48_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis, \u201cOn Isomorphisms and Density of NP and Other Complete Sets\u201d, SIAM J. of Comput 6 (1977) 305\u2013322.","journal-title":"SIAM J. of Comput"},{"key":"48_CR2","doi-asserted-by":"crossref","unstructured":"J. Berstel and C. Reutenauer, Rational Series and Their Languages, EATCS Monographs on Theoretical Computer Science, edited by Brauer, Rozenberg, and Salomaa, Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-73235-5"},{"key":"48_CR3","doi-asserted-by":"crossref","unstructured":"J. Brzozowski, \u201cOpen Problems about Regular Languages\u201d, Formal Language Theorem \u2014 Perspectives and Open Problems, pp. 23\u201348, edited by R. V. Book, 1980.","DOI":"10.1016\/B978-0-12-115350-2.50007-5"},{"key":"48_CR4","volume-title":"Basic Techniques of Combinatorial Theory","author":"D. I. A. Cohen","year":"1978","unstructured":"D. I. A. Cohen, Basic Techniques of Combinatorial Theory, John Wiley & Sons, New York, 1978."},{"key":"48_CR5","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0166-218X(82)90072-5","volume":"4","author":"K. Culik II","year":"1982","unstructured":"K. Culik II, F.E. Fich and A. Salomaa, \u201cA Homomorphic Characterization of Regular Languages\u201d, Discrete Applied Mathematics 4, (1982)149\u2013152.","journal-title":"Discrete Applied Mathematics"},{"key":"48_CR6","unstructured":"S. Eilenberg, Automata, Languages and Machines, vol. A, Academic Press, 1974."},{"key":"48_CR7","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley (1979), Reading, Mass."},{"key":"48_CR8","doi-asserted-by":"crossref","unstructured":"W. Kuich and A. Salomaa, Semirings, Automata, Languages, Springer-Verlag, 1986.","DOI":"10.1007\/978-3-642-69959-7"},{"issue":"no.6","key":"48_CR9","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B. Ravikumar","year":"1989","unstructured":"B. Ravikumar and O. H. Ibarra, \u201cRelating the type of ambiguity of finite automata to the succintness of their representation\u201d, SIAM J. Comput. vol. 18, no. 6 (1989) 1263\u20131282.","journal-title":"SIAM J. Comput."},{"key":"48_CR10","unstructured":"A. Salomaa, Computation and Automata, Encyclopedia of Mathematics and Its Applications, vol. 25. Cambridge University Press, 1985."},{"key":"48_CR11","doi-asserted-by":"crossref","unstructured":"A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series, Springer-Verlag, 1978.","DOI":"10.1007\/978-1-4612-6264-0"},{"key":"48_CR12","unstructured":"J. Shallit, \u201cNumeration Systems, Linear Recurrences, and Regular Sets\u201d, Research Report CS-91-32, Dept. of Computer Science, Univ. of Waterloo, 1991."},{"key":"48_CR13","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0019-9958(62)90244-9","volume":"5","author":"M. P. Sch\u00fctzenberger","year":"1962","unstructured":"M. P. Sch\u00fctzenberger, Finite Counting Automata, Information and Control, 5 (1962) 91\u2013107.","journal-title":"Information and Control"},{"key":"48_CR14","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0166-218X(88)90083-2","volume":"20","author":"S. Yu","year":"1988","unstructured":"S. Yu, \u201cCan the Catenation of Two Weakly Sparse Languages be Dense?\u201d, Discrete Applied Mathematics 20 (1988) 265\u2013267.","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1992"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55808-X_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:01:53Z","timestamp":1605646913000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55808-X_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540558088","9783540472919"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-55808-x_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}