{"entities":{"Q794443":{"pageid":796291,"ns":120,"title":"Item:Q794443","lastrevid":48715531,"modified":"2026-01-05T17:01:59Z","type":"item","id":"Q794443","labels":{"en":{"language":"en","value":"Finite-state \\(\\omega\\)-languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3860419"}},"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":"Q794443$7CA037D8-D659-47D4-9AB2-F9E12CFF549C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ae383aa340be0c5a4c46cbe8e0b926ceb15ab3a5","datavalue":{"value":{"text":"Finite-state \\(\\omega\\)-languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q794443$4F1A0E93-2783-4B80-B519-DAA5987DC6B9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8c4b7c2b23777ae0ef26be998f6f033b66197cdc","datavalue":{"value":"0541.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794443$61F20372-9068-47E1-8DAE-4038EE33E6B0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"97dff63429fad50a507d82d7d895a71fec27f8a7","datavalue":{"value":"10.1016/0022-0000(83)90051-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794443$0E31D23A-39B2-441E-B0C1-F6F48071FA5C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2387e3951e6b46186df54cdfd5817208989946cb","datavalue":{"value":{"entity-type":"item","numeric-id":259038,"id":"Q259038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$09350E52-F719-4F2C-8967-F7CC9E6E6589","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$25897D54-F340-4303-97C8-B2F3551A315A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q794443$9F424692-836F-46F5-B68E-52D80BB8BB2A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c3133446c808b7207963e2a9d2d49dfa908dfe7b","datavalue":{"value":"This is an important paper about the basics of sets of infinite sequences of words, customarily referred to as \\(\\omega\\)-languages. In particular, the paper is a contribution to the theory of finite-state \\(\\omega\\)- languages introduced by \\textit{B. A. Trakhtenbrot} [Sib. Math. Zh. 3, 103- 131 (1962; Zbl 0115.007)]. The paper under review discusses the problem to what extent the class of finite-state \\(\\omega\\)-languages and the class of regular \\(\\omega\\)-languages coincide. The earlier investigations along these lines [e.g., \\textit{M. Linna}, Inf. Control 31, 272-293 (1976; Zbl 0329.68066)] have shown that the restriction of computational power is not successful to topological considerations, estimating the exact borderline in the Borel hierarchy between the ranges where all finite-state \\(\\omega\\)-languages are regular and where not. To this end, some general properties of both regular and finite-state \\(\\omega\\)-languages are established. As a by-result a partial solution to the minimization problem for finite automata accepting regular \\(\\omega\\)-languages is obtained.","type":"string"},"datatype":"string"},"type":"statement","id":"Q794443$D8DAA6F5-62BC-4E7C-BA3E-20FB5B9CA1C2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794443$C07BA309-88A8-4334-A845-9737CCFDFBF0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e04319f127446f90b2c171e0424acb6e3186feaf","datavalue":{"value":"3860419","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794443$E41E4C92-1793-4F50-9955-037DE9528BB3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c22b99ac6b8b031ba289a5388fa31a3c1e9cb32","datavalue":{"value":"finite state omega-languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q794443$C3DDEBB2-021C-40E1-AF73-7C4F67694295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71c9f7876c7a7997f9f09605fd30886b416c7209","datavalue":{"value":"regular omega-languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q794443$A5CFE75C-CFD7-4E14-A97D-C88DF828DD1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"983f412e6a1c2f19370243e260e05b8fbea48da1","datavalue":{"value":"infinite sequences of words","type":"string"},"datatype":"string"},"type":"statement","id":"Q794443$6F372E48-049C-439D-8D63-83FC22F4E45C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"186b8f1fa1773e57f7c0d134ac268188b71c1b27","datavalue":{"value":"topological considerations","type":"string"},"datatype":"string"},"type":"statement","id":"Q794443$EE97F670-63F2-431D-81AB-0496B1123303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af47dd0d79a1f58f2e4b3e8819f78e985cf685b3","datavalue":{"value":"Borel hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q794443$64C9557C-B6F7-466D-81AE-16100510B677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c6bf197a3521f2ef0c77ff582b65a86030f9ca2","datavalue":{"value":"minimization problem for finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q794443$675D1647-177A-481D-A820-519DEA699CB1","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":"Q794443$D6A90CC1-BD78-4E47-8423-39BEE0F002E3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"41e7ff1139dda6caf30f086ee8bbcc3bc037598a","datavalue":{"value":{"entity-type":"item","numeric-id":5632482,"id":"Q5632482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$DA12D354-79CE-4B7E-9891-E0BD84603FDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbf4dae9a78ba0faf4348899879d3cffee2a4636","datavalue":{"value":{"entity-type":"item","numeric-id":5618355,"id":"Q5618355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$E5CB0C38-1DE0-45D4-877F-FD1EC3887B55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af5d1a78a8dd9095d53b8a39c1445c835e906c59","datavalue":{"value":{"entity-type":"item","numeric-id":5609381,"id":"Q5609381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$D2647D43-40B6-4E43-A792-9DCA6E4370F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e4c9eb0bc39c2db4fa09c1fc685181796f068e9","datavalue":{"value":{"entity-type":"item","numeric-id":1211504,"id":"Q1211504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$2ADAF1D2-5DDD-4AAF-AB4B-5A00D891FE20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a41da88234adbed83efe7412ca5c92908a4dda70","datavalue":{"value":{"entity-type":"item","numeric-id":1240574,"id":"Q1240574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$619939CD-5DD5-4E28-855C-680436D5573C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4026710286be0e296501d6694a98ee92e525c96","datavalue":{"value":{"entity-type":"item","numeric-id":1247962,"id":"Q1247962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$87AF4E15-624E-4855-90FB-ADD217D43059","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b09d67d7f1821ad4236528c6278ed053a02c1df","datavalue":{"value":{"entity-type":"item","numeric-id":2265218,"id":"Q2265218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$DA3D7420-AA98-4725-8849-B82D7277B4A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18bed1a36581c9b2ae1776792e0a065a6aa1bc9d","datavalue":{"value":{"entity-type":"item","numeric-id":4138628,"id":"Q4138628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$180E383D-46DD-47C2-B61B-AEA486C953D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73a0a2b15e99842c46a5657e247bbb4d0ca5dfbc","datavalue":{"value":{"entity-type":"item","numeric-id":4095899,"id":"Q4095899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$826B8241-AC7B-4124-AA3A-7D55A0960C11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a5aa94c8e45c27c05c3a12795740c87d5e2ef2f","datavalue":{"value":{"entity-type":"item","numeric-id":5613960,"id":"Q5613960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$E1671308-7476-41A6-B64B-C6EF0EC72542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd2f45038ab8e4e4836ac8e04a5fbfcb672edc4f","datavalue":{"value":{"entity-type":"item","numeric-id":5588675,"id":"Q5588675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$684FCE77-7649-42D2-BB06-7288A39F0C58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f294e095856a4a454ad9f0e895751576999ab34","datavalue":{"value":{"entity-type":"item","numeric-id":4115102,"id":"Q4115102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$254617F6-EEBD-4E3D-99A0-A2F46985D2AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c67b912da25dffe3507046153d6cb433cd02d4d","datavalue":{"value":{"entity-type":"item","numeric-id":3899534,"id":"Q3899534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$31AEDC4B-70F4-40FA-989B-F7F76E1A216D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f24dde664dec592aaf2efc66afcadf834211d90","datavalue":{"value":{"entity-type":"item","numeric-id":4055589,"id":"Q4055589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$1EB2F98C-12AB-4820-9143-8D67800655B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"000c6e3680f801318aa34bfabb01fb0af531ed28","datavalue":{"value":{"entity-type":"item","numeric-id":5723183,"id":"Q5723183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$3D9E851B-B35A-4C2C-BF74-CE4F4816482A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd1e092eb099a32d4d756ee9e4c56322cfbee0af","datavalue":{"value":{"entity-type":"item","numeric-id":3873568,"id":"Q3873568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$2147E6DD-A296-4F44-9E7E-54FF1D967647","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b006b8c69e155d429c6f2e527a477171a2179d5","datavalue":{"value":{"entity-type":"item","numeric-id":3335014,"id":"Q3335014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794443$3B43958E-3FBE-4091-A9DE-6B789C2FB0E6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39c086e17af8111efcf3ebaf3af821b36ccf727e","datavalue":{"value":{"entity-type":"item","numeric-id":3777489,"id":"Q3777489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf559efd5bf4a11f225d15a3f57369c8dd57dd30","datavalue":{"value":{"amount":"+0.8181095719337463","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":"Q794443$9F0E6F3F-A8F6-4751-A783-8D401659CDB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ecd3a7afc979ba117f58586761a08d8608a5ea5","datavalue":{"value":{"entity-type":"item","numeric-id":3167506,"id":"Q3167506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3dae460ffdd1798fd21da48a8ae11a764e60f065","datavalue":{"value":{"amount":"+0.810258150100708","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":"Q794443$6CB6667B-0C8C-479B-A93C-C1F219F179A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"663d441460a1530f71e776b6a6b43b67c87ee3d5","datavalue":{"value":{"entity-type":"item","numeric-id":4299865,"id":"Q4299865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e3db2f5eca632e420a9e534fe87a19f0d562fc0","datavalue":{"value":{"amount":"+0.8010019659996033","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":"Q794443$1740FCE8-B3E4-491E-8061-3F3EDD771731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c002d09d0cf543fd6e52cb16c2bbffcb9523589","datavalue":{"value":{"entity-type":"item","numeric-id":1184990,"id":"Q1184990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5a0cc86862dac9f94fc5c195934598de5604352","datavalue":{"value":{"amount":"+0.7993993163108826","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":"Q794443$412F2C15-9D88-49BA-8E8B-28AC476C4EEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85e1be1d07684bf9d201eb1c4fd043042609dddc","datavalue":{"value":{"entity-type":"item","numeric-id":1127314,"id":"Q1127314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2099c833bae790d87cfbf8807dc7da3179e19443","datavalue":{"value":{"amount":"+0.7876245379447937","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":"Q794443$3E7B2E45-C340-4324-85BE-852214632821","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:794443","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:794443"}}}}}