{"entities":{"Q1120286":{"pageid":1131035,"ns":120,"title":"Item:Q1120286","lastrevid":67048554,"modified":"2026-04-12T14:35:04Z","type":"item","id":"Q1120286","labels":{"en":{"language":"en","value":"On the valuedness of finite transducers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4100616"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120286$71CB5F52-258E-4C34-91BD-B57C7A821B8F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9bf930f42e2db855d6af47d5219673f48326930b","datavalue":{"value":{"text":"On the valuedness of finite transducers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1120286$8A9C1738-4F65-4E83-8D4F-742C7D4EFD2F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aae7ba1ac8e16261f9de0fbca214bc2efe3cbfc1","datavalue":{"value":"0672.68027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120286$C5AE810F-33D9-4CAE-9282-132D6F712EBB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eef83e20e842d285d000fd48f0ecd2e5382df7c2","datavalue":{"value":"10.1007/BF00264285","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120286$5D484B57-BEE2-4D64-A5F3-86E1142126A6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aedf720352fcca932fab3523c4bbcafd7c4c7cdb","datavalue":{"value":{"entity-type":"item","numeric-id":1104176,"id":"Q1104176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120286$0E4024F5-417E-489F-B225-955DCF80026B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120286$2BADBCC0-7A8A-436D-8BDB-48312DCD83B1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1120286$3D65A950-A184-4EEF-AD72-583B32648032","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"72cc9a87c676a8fd1a4b7c351fb1036328188b2b","datavalue":{"value":"We investigate the valuedness of finite transducers in connection with their inner structure. We show: the valuedness of a finite-valued nondeterministic generalized sequential machine (NGSM) M with n states and output alphabet \\(\\Delta\\) is at most the maximum of \\((1-\\lfloor 1/\\#\\Delta \\rfloor)\\cdot (2^{k_ 1}\\cdot k_ 3)^ n\\cdot n^ n\\cdot \\#\\Delta^{n^ 3\\cdot k_ 4/3}\\) and \\(\\lfloor 1/\\#\\Delta \\rfloor \\cdot (2^{k_ 2}\\cdot k_ 3\\cdot (1+k_ 4))^ n\\cdot n^ n\\) where \\(k_ 1\\leq 6.25\\) and \\(k_ 2\\leq 11.89\\) are constants and \\(k_ 3\\geq 1\\) and \\(k_ 4\\geq 0\\) are local structural parameters of M. There are two simple criteria which characterize the infinite valuedness of an NGSM. By these criteria, it is decidable in polynomial time whether or not an NGSM is infinite-valued. In both cases, {\\#}\\(\\Delta\\) \\(>1\\) and {\\#}\\(\\Delta\\) \\(=1\\), the above upper bound for the valuedness is almost optimal. By reduction, all results can be easily generalized to normalized finite transducers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120286$452618E9-0A75-45E2-AE3A-7BA3A01AE6B6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120286$B1D52E82-252D-40BF-962D-14E81DD8F312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120286$A716CAFE-7B34-4717-B9BD-7BF805DF3ABA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1e726656302d06b22c88055efe1ed874248403d6","datavalue":{"value":"4100616","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1120286$D93A24F1-D21F-4737-8DE3-8746944C62C1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0b60a966eaef6ee1a427ce569ee7dd449a4cf2a","datavalue":{"value":"finite-valued nondeterministic generalized sequential machine M","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120286$440F2E61-EE62-467E-84F3-DD84607AA40F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59b138e7ce19428b8b69ec2027b1eb14ec321aac","datavalue":{"value":"valuedness of finite transducers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1120286$20B72BAB-6CD3-4D9A-9A75-376D14BDCB1E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"93452070dd8bd242d8a0107264a79648a2be13cc","datavalue":{"value":{"entity-type":"item","numeric-id":410093,"id":"Q410093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120286$BE3452EA-1125-49D8-B176-47FB5BCFC144","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1120286$BB116FC7-B254-4D15-84CD-892178F5D1AD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc7c38e72be8f0eff9866845ee1cfd8572ebde50","datavalue":{"value":{"entity-type":"item","numeric-id":4037692,"id":"Q4037692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70e222466883747ead18beaea9eae0b070c5f88b","datavalue":{"value":{"amount":"+0.90835440158844","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1120286$BAED3C40-B220-4203-ACFB-ADED7A7F2699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30326973e624a1c18defe5ceacee12f266b5e8c2","datavalue":{"value":{"entity-type":"item","numeric-id":3975172,"id":"Q3975172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f75562fd6b2927c64e4e668b98db939987e14c96","datavalue":{"value":{"amount":"+0.899853527545929","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1120286$50D08704-85CC-40DB-97A1-928EED14A4FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89c3a0d50a2b7320f562cc7a212a1fe16a5ffc7c","datavalue":{"value":{"entity-type":"item","numeric-id":1323379,"id":"Q1323379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8afe4193701bfc2790ad44fde34d3da663594def","datavalue":{"value":{"amount":"+0.8598278164863586","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1120286$3FE4C9E2-D5EF-4FFC-BB83-61EB0A96C9B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e5d221cf48d78fc7414d6d9c6041b3d9ee07a4b","datavalue":{"value":{"entity-type":"item","numeric-id":3599160,"id":"Q3599160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3df6ea5921a891b62269151c1350915e50f4125d","datavalue":{"value":{"amount":"+0.8572255373001099","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1120286$0DF5DA3E-20EA-448D-B823-28068A1462D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8040ca32200967fb1b44a82191fc616b9de280e8","datavalue":{"value":{"entity-type":"item","numeric-id":2672252,"id":"Q2672252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5cf1064f160075d87b5da84d00d7e031d1d1d5f","datavalue":{"value":{"amount":"+0.8507710099220276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1120286$74D5BF67-07B8-4DF4-8ECC-72BA162DA590","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the valuedness of finite transducers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_valuedness_of_finite_transducers"}}}}}