{"entities":{"Q800737":{"pageid":802585,"ns":120,"title":"Item:Q800737","lastrevid":64469223,"modified":"2026-04-11T20:04:52Z","type":"item","id":"Q800737","labels":{"en":{"language":"en","value":"Characterization of \\(\\omega\\)-regular languages by first-order formulas"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3878387"}},"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":"Q800737$26895C56-F889-4D82-927C-DF4536AB4A0B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ea10f6b68e534424bf924d27af34327898b9b8b7","datavalue":{"value":{"text":"Characterization of \\(\\omega\\)-regular languages by first-order formulas","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q800737$B5FF557B-6870-43AA-8CD4-5D43DD0FA489","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f7fefa12b7ad805b7f13c72fc38390fc308133dc","datavalue":{"value":"0551.68069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800737$B719491A-F3A6-496A-BA10-EBA8FB5B1738","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ed82d65357cdf2f2acb2ebabf57239c7b7a69472","datavalue":{"value":"10.1016/0304-3975(83)90027-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800737$F1F0BF26-89C1-4AEC-958E-DDF7949E8453","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0acb7f854d571dfd732e73bdce7fdc7d33efe8dc","datavalue":{"value":{"entity-type":"item","numeric-id":198194,"id":"Q198194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800737$8EF3B7A8-2F3E-462C-AA46-2A9A9CAFE093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eae9e9e2bcb0b4d1a7490122f456e3c72f7ac9b4","datavalue":{"value":{"entity-type":"item","numeric-id":800092,"id":"Q800092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800737$8F7D1656-A299-47E3-892C-93D73430D375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c47cb944061dc1b1d876a76d5d622e81452c161","datavalue":{"value":{"entity-type":"item","numeric-id":671413,"id":"Q671413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800737$9B325359-551B-428E-A7D8-109638B0C56B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800737$90CCAD35-2100-4D33-86E4-A7A534E6735A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q800737$FC6111A5-ADE4-4C7B-9769-5B681C2A7905","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e6b2f4cc155107c57079442e534434d0ee1d54eb","datavalue":{"value":"An \\(\\omega\\)-language over some finite alphabet A is a set of countable sequences over A. A finite automaton M can be used to define such languages; e.g. that M visits a certain state infinitely often while reading the sequence. With each finite automaton a first order language is associated. The atomic formulas are \\(P_ s(t)\\), \\(t<t',\\quad t=t',\\) here t runs over a discrete time structure and \\(P_ s(t)\\) means that M is in state s at time t. The purpose of this paper is to compare two different kinds of definability for \\(\\omega\\)-languages: Acceptance by various kinds of automata and definability by formulae with a bounded number of quantifier changes. Among the results proved are characterizations of co-regular languages in general and those satisfying certain conditions, e.g. being a countable union of closed sets.","type":"string"},"datatype":"string"},"type":"statement","id":"Q800737$178C1478-A505-4EC1-BF43-A051A3A1BBDF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800737$20467B31-C272-422D-A53A-B3B32076F6EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"abca938afd309309893053e8ee4f51374fed9de6","datavalue":{"value":"03C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800737$AD7D07BD-11BC-42BC-B8C5-B144879693C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c1d2d83da0d870574277144fdd1db9abaae162ec","datavalue":{"value":"03C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800737$6B713F01-959A-4C26-B6FB-9869963201AF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e38a469927365dbe7142a0614635a9ba2468161a","datavalue":{"value":"3878387","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800737$62EA5505-F8A5-407D-852C-7C280C1144B7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99574e7068089b4c1b110cf1bc48234726af7fe7","datavalue":{"value":"omega language","type":"string"},"datatype":"string"},"type":"statement","id":"Q800737$4FB255D5-60AC-40BF-9635-CF9950BC5054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05ac3aa141a5e99f6d4ec0321d581483dfafb5e9","datavalue":{"value":"finite automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q800737$2110A4E7-DAE5-4339-83F8-9FCED517C009","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1136f787679a6c82c64749ca14e20e19be9c8e49","datavalue":{"value":"first order language","type":"string"},"datatype":"string"},"type":"statement","id":"Q800737$BDDF968B-B4FA-4951-A6C3-761C41155643","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2ac3f30d773ef1894fb2eb52711e135b17d0158","datavalue":{"value":"definability","type":"string"},"datatype":"string"},"type":"statement","id":"Q800737$5C4F8B0E-C428-48D0-A738-B89E941E1CED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e00b7bc278ce30fea0c68ed628bed6ac7fc2292","datavalue":{"value":"co- regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q800737$5AD73302-184B-48A4-BCAB-850A07237BA6","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":"Q800737$B3D6FBF9-E307-43DD-8667-C7554D931019","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5f501aa43a655a5bfb67d47941e98e2a1b6e0c8d","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90027-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q800737$85EA2A19-D5FC-4E77-A2FE-286987147220","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"df9847a6c93ed40d8be6b5b8291302af24543010","datavalue":{"value":"W2044335913","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800737$3D37E1AA-8EC8-4545-9404-2517A1F5589C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"36d84aa78f0d96f7d40459af01bc21793f5962fa","datavalue":{"value":{"entity-type":"item","numeric-id":4079524,"id":"Q4079524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800737$B86B4A19-30AF-42DF-97BB-E32F803E6C9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a592cba5bd50a769a8b95145033ff13a570cf73","datavalue":{"value":{"entity-type":"item","numeric-id":5573396,"id":"Q5573396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800737$ACB08B29-6532-4500-A55E-8D3D348D533B","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":"Q800737$4568F617-1117-4EB8-8E02-CF008C695330","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75292f6880dd3275361618ebb07df15f46377e02","datavalue":{"value":{"entity-type":"item","numeric-id":4074888,"id":"Q4074888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800737$42948560-A3AB-4CD8-A9E7-97A3902B00AB","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":"Q800737$9132A346-781D-4E01-812E-ABACBDC4CFDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3827186477a7d381cac7f7da7e9d4143139fcfe2","datavalue":{"value":{"entity-type":"item","numeric-id":1053464,"id":"Q1053464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800737$0FD5369C-A7B8-4EB4-B6C4-11DFC8D6A42F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1a24b75fa6c5928ce8df6944f94b49b2c174aca","datavalue":{"value":{"entity-type":"item","numeric-id":1822511,"id":"Q1822511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a54f495f5cef1c996d2aa5281dca007dd96ebb6","datavalue":{"value":{"amount":"+0.8450223207473755","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":"Q800737$14196335-D206-4D41-8339-906C4FA1316F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27fb2f63f7b5d855a5f97af530f35f6431eb6185","datavalue":{"value":{"entity-type":"item","numeric-id":3693520,"id":"Q3693520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77dac723c753dd9daec4841be1919671b7de031a","datavalue":{"value":{"amount":"+0.8259994387626648","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":"Q800737$28EAD7E0-A7F0-4FE8-8AD3-D5799FDEDF7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9744f14dace30910cc69859cd7b8a9c21053e28f","datavalue":{"value":{"entity-type":"item","numeric-id":3086925,"id":"Q3086925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85adb7f95a59cf930ba96ec843500ab7db7d0966","datavalue":{"value":{"amount":"+0.8236293792724609","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":"Q800737$4F098D69-3C05-4F90-8F04-2D94998830A8","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":"db632acd4c2df3241f261332b123deb808c84863","datavalue":{"value":{"amount":"+0.8092482686042786","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":"Q800737$9821EC08-58FE-41B7-8970-41A537D510D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a53a15ef638d4855ae4e6c874fb67227a0dfcf2f","datavalue":{"value":{"entity-type":"item","numeric-id":1116351,"id":"Q1116351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d541bd27b34644b2c236fb0c9bd5fcce49f3fc63","datavalue":{"value":{"amount":"+0.8055816888809204","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":"Q800737$386519E8-93E7-44D1-88D6-569DF165E140","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Characterization of \\(\\omega\\)-regular languages by first-order formulas","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Characterization_of_%5C(%5Comega%5C)-regular_languages_by_first-order_formulas"}}}}}