{"entities":{"Q1323379":{"pageid":1334129,"ns":120,"title":"Item:Q1323379","lastrevid":68462205,"modified":"2026-04-12T23:52:20Z","type":"item","id":"Q1323379","labels":{"en":{"language":"en","value":"On the lengths of values in a finite transducer"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 567333"}},"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":"Q1323379$952E4A7C-BB5B-410F-A974-84B840839928","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2204e6d0a7450c7ab8cc36dcb9e71d950dce826f","datavalue":{"value":{"text":"On the lengths of values in a finite transducer","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1323379$E8347EBE-8C3C-4AD6-8A9E-5A13FD0E0AED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"52dc9b317307a7eab320b67fd2b027ce95d629f0","datavalue":{"value":"0790.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323379$E977BE60-7892-4E59-9B62-02379ED3341B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8fcf05d20668971ddce88e091c3a911c364ac751","datavalue":{"value":"10.1007/BF01185566","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323379$C6624B77-8637-4438-A351-60117339191B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"24d2f620d2974ebdd1015229debd06431f4c7398","datavalue":{"value":{"entity-type":"item","numeric-id":1294575,"id":"Q1294575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$68FC702C-C5FA-4DAA-B8D3-888ADE3F3575","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":"Q1323379$C9D036F3-1893-40BC-9376-0431E1BDFDCB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8b439a09488bc2e6cdbf4d00c3a7f90f1bcfc4c1","datavalue":{"value":{"time":"+1994-07-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1323379$7AC7846F-FC2D-467B-A6CF-05CFE07E884E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c2ac97c006b82ac1401bc4edb1e31ebcd7f879b6","datavalue":{"value":"We investigate finite transducers and their inner structure with regard to the lengths of values. Our transducer models are the normalized finite transducer (NET) and the nondeterministic generalized sequential machine (NGSM), which is a real-time NFT. The length-degree of an NFT is defined to be the maximal number of different lengths of values for an input word or is infinite, depending on whether or not a maximum exists. We show: An NGSM \\(M\\) with finite length-degree can be effectively decomposed into finitely many NGSMs \\(M_ 1,\\dots,M_ N\\) having length-degree at most 1 such that the transduction realized by \\(M\\) is the union of the transductions realized by \\(M_ 1,\\dots,M_ N\\). Using this decomposition, the equivalence of NGSMs with finite length-degree is recursively decidable. Whether or not an NGSM has finite length-degree can be decided in deterministic polynomial time. By reduction, all these results can be generalized to NFTs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323379$5A9F1FB2-1C02-4A19-955D-2D056976A5FA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323379$279854EF-35C6-4D37-A83E-CF6A415FDB14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323379$36E6FF98-2EBE-4268-B717-5058CA230B60","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1802b1bf3539c0f252657df89d8fa258b0ae2364","datavalue":{"value":"567333","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323379$639AAF04-C4FF-49EC-9202-0E5CD88B26DE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6cdfe35a4a8e27d801d83a2628f570228a2f2964","datavalue":{"value":"normalized finite transducer","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323379$F1B3F15F-57ED-4632-B8DE-5E126D326CED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"060c726ea66d21aa1542ff88a4be349aa1a62250","datavalue":{"value":"nondeterministic generalized sequential machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323379$4342F00C-A200-46CC-A3CA-16745C738DE6","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":"Q1323379$090DA7BC-83BD-4E41-A82C-206836CEE77D","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":"Q1323379$1CDC39D7-AD59-4CA8-8010-2656A28C29F9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$935A2571-4C7E-46F6-AD37-AFF5014F1E67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3632afaf7c9124694de853efafd5cd84e2a50881","datavalue":{"value":{"entity-type":"item","numeric-id":3859267,"id":"Q3859267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$9DFAE28C-4998-4463-9883-8305C0796280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"002cdf925f6811f591bec8bc5e91353e7e1aa8e8","datavalue":{"value":{"entity-type":"item","numeric-id":1242878,"id":"Q1242878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$CE22CA60-D0CE-412A-A3CF-93FBD77F902B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"221055f6017496ee1a8c8d0edc165172a100935e","datavalue":{"value":{"entity-type":"item","numeric-id":913523,"id":"Q913523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$1AEC6601-BC39-4E75-A6AA-2EC19501C1D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"239e14608bb684951922f9c8bb30036c33157150","datavalue":{"value":{"entity-type":"item","numeric-id":1090467,"id":"Q1090467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$147DFB16-554B-498C-B6E6-2777DF072006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fce6b15d7f7c38b132fff8d032bbd1c4bb01ae91","datavalue":{"value":{"entity-type":"item","numeric-id":4035657,"id":"Q4035657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$59E64A91-96F9-4B60-89ED-6FEC9561BAC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"958e8bf05dd41a356ed45fa949d36e2ba662ac79","datavalue":{"value":{"entity-type":"item","numeric-id":5544289,"id":"Q5544289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$332566B9-B03A-44C6-B036-9F6AB45B428B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c67e7310d71a3ff5db7aa06fe30017f241c342d5","datavalue":{"value":{"entity-type":"item","numeric-id":3968472,"id":"Q3968472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$742D1EE8-1790-42A2-929F-8164AD24F950","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$D1A3BEE4-C0FA-4E87-AD1B-9930CDC20F72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9684d84be3b8355a2edee9961c6843594427ba04","datavalue":{"value":{"entity-type":"item","numeric-id":4167584,"id":"Q4167584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$33F09676-BF01-4678-8AA8-B7B0721E972C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f371e726c563572dbd8cc826d809cb811146aa6","datavalue":{"value":{"entity-type":"item","numeric-id":3315002,"id":"Q3315002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$42AE0257-088A-43B2-88BD-51A6BB5B516D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e808fbea015adf180aedd7aaad2f4dd7b882d2a2","datavalue":{"value":{"entity-type":"item","numeric-id":1255319,"id":"Q1255319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$F5390304-8893-4C0E-AA6F-68DD5BC83069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc974d370f3f3f2c0fa14da1160bbca2b962ae53","datavalue":{"value":{"entity-type":"item","numeric-id":1238433,"id":"Q1238433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$5DDF4287-39EF-478F-96DE-BC34EDD6F91B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c8e38a0f004ff25f744a39b8197ce49ff3b22c2","datavalue":{"value":{"entity-type":"item","numeric-id":4027634,"id":"Q4027634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$E2D6D3C7-84A7-4597-9EFA-CD7FB8BA3E72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f4a9f58ed78bdd3bc1680086a81cd74444e0373","datavalue":{"value":{"entity-type":"item","numeric-id":3975172,"id":"Q3975172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$58664FD5-2CC2-4D47-832D-ECFFE1705104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b14874328e06322f55427a98ad1a9767d46fe80","datavalue":{"value":{"entity-type":"item","numeric-id":1120286,"id":"Q1120286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323379$D1F1EEC7-6EB8-424C-A3A3-69BB96E81F51","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e52c06330df25b47db2a3869cc99f641d21319fe","datavalue":{"value":"https://doi.org/10.1007/bf01185566","type":"string"},"datatype":"url"},"type":"statement","id":"Q1323379$08BC498B-C2BA-415E-AE2A-5F386BCAC8D0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6eb6cc26f0686fb0485b32a42c500e53b26c8bdf","datavalue":{"value":"W2006777369","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323379$8C3ED732-987F-48E0-A615-53286DB0DBA7","rank":"normal"}],"P1643":[{"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":"3515815a571e6a8cd2f12a63e00640ae6a02edcd","datavalue":{"value":{"amount":"+0.9665421843528748","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":"Q1323379$C634D739-A834-44E6-89DA-9DCAF24CED14","rank":"normal"},{"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":"e8963e048d11ae2c1ee15aefc39949f2fe938344","datavalue":{"value":{"amount":"+0.879848062992096","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":"Q1323379$8DCE03A9-878D-4D04-A77F-E6DA0400CA1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"786aa4d8e8af5df9033b96739f2aaea70aa0e5cd","datavalue":{"value":{"entity-type":"item","numeric-id":1120286,"id":"Q1120286"},"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":"Q1323379$37491824-22A5-46F0-890A-FCDCDDADCA89","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the lengths of values in a finite transducer","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_lengths_of_values_in_a_finite_transducer"}}}}}