{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:32Z","timestamp":1725663692297},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_175","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:20:13Z","timestamp":1330262413000},"page":"607-618","source":"Crossref","is-referenced-by-count":3,"title":["Economy of description for single-valued transducers"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Weber","sequence":"first","affiliation":[]},{"given":"Reinhard","family":"Klemm","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"49_CR1","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0022-0000(87)90008-0","volume":"34","author":"K. Abrahamson","year":"1987","unstructured":"K. Abrahamson, Succinct representation of regular sets using gotos and Boolean variables, J. Computer and System Sciences 34 (1987) 129\u2013148.","journal-title":"J. Computer and System Sciences"},{"key":"49_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-663-09367-1","volume-title":"Transductions and Context-Free Languages","author":"J. Berstel","year":"1979","unstructured":"J. Berstel, Transductions and Context-Free Languages, Teubner, Stuttgart, 1979."},{"key":"49_CR3","unstructured":"C. Choffrut, Contribution \u00e0 l'\u00e9tude de quelques familles remarquables de fonctions rationnelles, th\u00e8se de doctorat d'\u00e9tat, Universit\u00e9 Paris VII, 1978."},{"key":"49_CR4","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0212019","volume":"12","author":"C. Choffrut","year":"1983","unstructured":"C. Choffrut and K. Culik II, Properties of finite and pushdown transducers, SIAM J. Computing 12 (1983) 300\u2013315.","journal-title":"SIAM J. Computing"},{"key":"49_CR5","series-title":"Lecture Notes in Computer Science 210","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/3-540-16078-7_78","volume-title":"Proc. 3rd STACS 1986","author":"C. Choffrut","year":"1986","unstructured":"C. Choffrut and M.P. Sch\u00fctzenberger, D\u00e9composition de fonctions rationnelles, Proc. 3rd STACS 1986, in: Lecture Notes in Computer Science 210, Springer, Berlin, Heidelberg, 1986, pp. 213\u2013226."},{"key":"49_CR6","volume-title":"Automata, Languages, and Machines, Volume A","author":"S. Eilenberg","year":"1974","unstructured":"S. Eilenberg, Automata, Languages, and Machines, Volume A, Academic Press, New York, NY, 1974."},{"key":"49_CR7","volume-title":"An Introduction to the Theory of Computation","author":"E. Gurari","year":"1989","unstructured":"E. Gurari, An Introduction to the Theory of Computation, Computer Science Press, Rockville, MD, 1989."},{"key":"49_CR8","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF01744569","volume":"16","author":"E. Gurari","year":"1983","unstructured":"E. Gurari and O. Ibarra, A note on finite-valued and finitely ambiguous transducers, Mathematical Systems Theory 16 (1983) 61\u201366.","journal-title":"Mathematical Systems Theory"},{"key":"49_CR9","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1051\/ita\/1992260302431","volume":"26","author":"T. Harju","year":"1992","unstructured":"T. Harju, H.C.M. Kleijn, and M. Latteux, Compositional representation of rational functions, RAIRO Informatique th\u00e9orique et Applications 26 (1992) 243\u2013255.","journal-title":"RAIRO Informatique th\u00e9orique et Applications"},{"key":"49_CR10","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/BF01185560","volume":"29","author":"T. Harju","year":"1992","unstructured":"T. Harju, H.C.M. Kleijn, and M. Latteux, Deterministic sequential functions, Acta Informatica 29 (1992) 545\u2013554.","journal-title":"Acta Informatica"},{"key":"49_CR11","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/978-1-4613-9323-8_19","volume-title":"Sequences II","author":"T. Head","year":"1993","unstructured":"T. Head and A. Weber, Deciding code related properties by means of finite transducers, in: Sequences II, (R. Capocelli, A. De Santis, and U. Vaccaro, eds.), Springer, New York, NY, Berlin, Heidelberg, 1993, pp. 260\u2013272."},{"key":"49_CR12","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, MA, 1979."},{"key":"49_CR13","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01189856","volume":"26","author":"C. Kintala","year":"1993","unstructured":"C. Kintala, K.-Y. Pun, and D. Wotschke, Concise representations of regular languages by degree and probabilistic finite automata, Mathematical Systems Theory 26 (1993) 379\u2013395.","journal-title":"Mathematical Systems Theory"},{"key":"49_CR14","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF00263994","volume":"13","author":"C. Kintala","year":"1980","unstructured":"C. Kintala and D. Wotschke, Amounts of nondeterminism in finite automata, Acta Informatica 13 (1980) 199\u2013204.","journal-title":"Acta Informatica"},{"key":"49_CR15","unstructured":"H. Leung, personal communication, 1991."},{"key":"49_CR16","doi-asserted-by":"crossref","unstructured":"H. Leung, Separating exponentially ambiguous NFA from polynomially ambiguous NFA, Proc. 4th ISAAC 1993, in: Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, to appear.","DOI":"10.1007\/3-540-57568-5_252"},{"key":"49_CR17","volume-title":"Combinatorial Group Theory","author":"R. Lyndon","year":"1977","unstructured":"R. Lyndon and P. Schupp, Combinatorial Group Theory, Springer, Berlin, Heidelberg, New York, NY, 1977."},{"key":"49_CR18","doi-asserted-by":"crossref","unstructured":"A. Meyer and M. Fischer, Economy of description by automata, grammars, and formal systems, Proc. 12th SWAT 1971, pp. 188\u2013191.","DOI":"10.1109\/SWAT.1971.11"},{"key":"49_CR19","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"20","author":"F.R. Moore","year":"1971","unstructured":"F.R. Moore, On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata, IEEE Transactions on Computers 20 (1971) 1211\u20131214.","journal-title":"IEEE Transactions on Computers"},{"key":"49_CR20","series-title":"Lecture Notes in Computer Science 583","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/BFb0023844","volume-title":"Proc. 1st LATIN 1992","author":"J.-E. Pin","year":"1992","unstructured":"J.-E. Pin, On reversible automata, Proc. 1st LATIN 1992, in: Lecture Notes in Computer Science 583, Springer, Berlin, Heidelberg, 1992, pp. 401\u2013416."},{"key":"49_CR21","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B. Ravikumar","year":"1989","unstructured":"B. Ravikumar and O. Ibarra, Relating the type of ambiguity of finite automata to the succinctness of their representation, SIAM J. Computing 18 (1989) 1263\u20131282.","journal-title":"SIAM J. Computing"},{"key":"49_CR22","series-title":"Lecture Notes in Computer Science 464","first-page":"62","volume-title":"Proc. 6th IMYCS 1990","author":"C. Reutenauer","year":"1991","unstructured":"C. Reutenauer, Subsequential functions: characterizations, minimization, examples, Proc. 6th IMYCS 1990, in: Lecture Notes in Computer Science 464, Springer, Berlin, Heidelberg, 1991, pp. 62\u201379."},{"key":"49_CR23","doi-asserted-by":"crossref","unstructured":"E.M. Schmidt, Succinctness of descriptions of context-free, regular, and finite languages, Ph.D. thesis, Cornell University, 1978.","DOI":"10.7146\/dpb.v7i84.6500"},{"key":"49_CR24","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0304-3975(76)90026-8","volume":"3","author":"M.P. Sch\u00fctzenberger","year":"1976","unstructured":"M.P. Sch\u00fctzenberger, Sur les relations rationnelles entre mono\u00cfdes libres, Theoretical Computer Science 3 (1976) 243\u2013259.","journal-title":"Theoretical Computer Science"},{"key":"49_CR25","series-title":"Lecture Notes in Computer Science 668","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/3-540-56610-4_69","volume-title":"Proc. 4th TAPSOFT 1993","author":"H. Seidl","year":"1993","unstructured":"H. Seidl, When is a functional tree transduction deterministic? Proc. 4th TAPSOFT 1993, in: Lecture Notes in Computer Science 668, Springer, Berlin, Heidelberg, 1993, pp. 251\u2013265."},{"key":"49_CR26","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1137\/0214044","volume":"14","author":"R. Stearns","year":"1985","unstructured":"R. Stearns and H. Hunt III, On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata, SIAM J. Computing 14 (1985) 598\u2013611.","journal-title":"SIAM J. Computing"},{"key":"49_CR27","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-642-77735-6_6","volume-title":"Kolmogorov Complexity and Computational Complexity","author":"V.A. Uspensky","year":"1992","unstructured":"V.A. Uspensky, Complexity and entropy: an introduction to the theory of Kolmogorov complexity, in: Kolmogorov Complexity and Computational Complexity, (O. Watanabe, ed.), Springer, Berlin, Heidelberg, 1992, pp. 85\u2013102."},{"key":"49_CR28","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1007\/BF00264285","volume":"27","author":"A. Weber","year":"1990","unstructured":"A. Weber, On the valuedness of finite transducers, Acta Informatica 27 (1990) 749\u2013780.","journal-title":"Acta Informatica"}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_175.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:14:02Z","timestamp":1605647642000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_175"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_175","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}