{"entities":{"Q4035239":{"pageid":6064959,"ns":120,"title":"Item:Q4035239","lastrevid":108767939,"modified":"2026-11-10T05:21:24Z","type":"item","id":"Q4035239","labels":{"en":{"language":"en","value":"Stochastic automata and length distributions of rational languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 176138"}},"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":"Q4035239$80B3AA65-949C-43E0-964E-9A169FF6E012","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"30e377f6ea6a9336cf775a5327b13dd4b72717c1","datavalue":{"value":"0778.68067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4035239$55F5373B-50DC-41DB-987B-C8EE63E35C55","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b3994b899c3b70eb5eb85227ae910a470b174035","datavalue":{"value":{"entity-type":"item","numeric-id":804716,"id":"Q804716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4035239$78BB86B8-8EAA-4CA4-BA4C-13E12C3A0053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"735ee5984b9b62ee30fa6c117eb197a65dd5cb17","datavalue":{"value":{"entity-type":"item","numeric-id":216237,"id":"Q216237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4035239$DA07B476-2D2B-41AC-968C-5DB85B828096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3684a3460666f284ed8323854830b824c056e5e9","datavalue":{"value":{"entity-type":"item","numeric-id":1023051,"id":"Q1023051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4035239$A862D5E8-8D0A-4A26-ADAC-83E6264CA78F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"abd8d5e490ea4daf6d00f9dd2f897565e059b6cc","datavalue":{"value":{"time":"+1993-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4035239$7D3FB2D5-EA46-40FE-8328-D4794FFB2B89","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4035239$048EDA4F-435B-4F65-8665-F6FC666DFBB1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1a8111b18bc4af9c724fda4fdf52d2c40c433faf","datavalue":{"value":"176138","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4035239$742072BE-0B2E-4B47-8A16-D75243ECB8B3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01588185e6a0ea452aabe243e9d0ed340c301288","datavalue":{"value":"rational language","type":"string"},"datatype":"string"},"type":"statement","id":"Q4035239$DA8C7453-18A3-4439-9672-11C13894CF03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56c28033cb3b317daa6543fb3ee4a46ce68ab1a6","datavalue":{"value":"one-letter stochastic automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q4035239$AE0D9C42-464C-42D6-8C8F-B2FD2F3644EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0c6aeb663588b6fe13394f900bdcd185874b78e","datavalue":{"value":"stochastic languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q4035239$9EC9AC4B-AAD8-4D47-A474-CC5D6AC063D4","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":"Q4035239$1D9C2E05-E921-470F-B219-71ACF16240F1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccffa9955502724fdd3d07f1698bc0d1c0c3fcaa","datavalue":{"value":{"entity-type":"item","numeric-id":3327722,"id":"Q3327722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5733e7819d6e14f04a0124f852541d224484db54","datavalue":{"value":{"amount":"+0.7888904213905334","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":"Q4035239$8806E53D-6386-46A0-A690-D1608F1EB7FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb62db39f08d17cde1fa1b5a1d309c10cc4cee6d","datavalue":{"value":{"entity-type":"item","numeric-id":5506337,"id":"Q5506337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76d84057e4e81be759d36bad381586bd1dc97086","datavalue":{"value":{"amount":"+0.7834032773971558","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":"Q4035239$0CD497C7-63FF-4B40-9EAE-6ADD2CF30118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e09ac224c3ea6e63ae2393893ae94409e1214b76","datavalue":{"value":{"entity-type":"item","numeric-id":5678784,"id":"Q5678784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eacdf3db2df621e5827a1cb0f2cf573a256cb5f8","datavalue":{"value":{"amount":"+0.7789997458457947","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":"Q4035239$AE06E7D9-8B73-4852-A60F-78C5B8209C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"522307deb7783cfdc5d54201cdfdad5429afad1f","datavalue":{"value":{"entity-type":"item","numeric-id":3327737,"id":"Q3327737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b4f7267a9c6a26ae683b824cce68e43325d193d","datavalue":{"value":{"amount":"+0.7638406753540039","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":"Q4035239$BA1262FA-F884-499A-BCEE-01C3907C5044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af23d1bdec2524e1d5384e0e43ac60e547ef4038","datavalue":{"value":{"entity-type":"item","numeric-id":5678783,"id":"Q5678783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"148e32702b79b5146105fc9b9a5e800a542e1e37","datavalue":{"value":{"amount":"+0.7607259750366211","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":"Q4035239$2EB1F7C6-37EF-42BE-8706-536CE9186E23","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f34ca67a3943e049bea6af544e07880e0514ddeb","datavalue":{"value":{"text":"Stochastic automata and length distributions of rational languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4035239$15C19B5B-FB91-46AD-85D7-A15073D5E789","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0b67a81c3b8728592f42e8af8d7e63afb11c93f4","datavalue":{"value":"10.1007/3-540-54345-7_61","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4035239$8C02D44D-93D1-4661-A250-378AFF8CD524","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7a0b40e3c25bc5fe53fa291e08bbb5b56dc24069","datavalue":{"value":"[For the entire collection see Zbl 0753.00030.] \\textit{D. Niwinski} [in ``Logics and recognizable sets'', Report on the Workshop ESPRIT-ASMICS N\\(^{\\circ}\\) 3166, Dersau, Germany, 24 (1990)] raised to two following questions: \\((Q1)\\) Does the set \\(\\{n\\in N\\mid | L\\cap \\{a,b\\}^ n| >2^{n- 1}\\}\\) belong to \\(Rat(N)\\)? \\((Q2)\\) Does the set \\(\\{w\\in \\{a,b\\}^*\\mid | w^{-1}L\\cap \\{a,b\\}^{p(| w|)}| >2^{p(| w|)-1}\\}\\) belong to Rat\\((\\{a,b\\}^*)\\)? We will see here that the two questions (Q1) and (Q2) are related, that their answers are positive for ``almost'' every rational language, but that counterexamples to both assertions can be found. Moreover it appears that question (Q1) is related to the theory of one-letter stochastic automata that was developed by \\textit{P. Turakainen} [On probabilistic automata and their generalizations, Ann. Acad. Scient. Fennicae, Series A, 429, 7-53, Helsinki (1969)]. We give a new and more concise presentation of Turakainen's results concerning this class of stochastic languages. We then address the two questions of Niwinski. With any rational language \\(L\\), we associate a stochastic automaton that computes the length frequencies of \\(L\\). Then, applying Turakainen's results, we obtain general classes of rational languages for which question (Q1) has a positive answer. Finally we show how to reduce question (Q2) to the first one.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4035239$6D96EE29-A7DA-4C5D-B42C-841BE6E3168D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4035239$354F3C56-DEBA-419A-A6A5-8A127F0F0D3E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Stochastic automata and length distributions of rational languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Stochastic_automata_and_length_distributions_of_rational_languages"}}}}}