{"entities":{"Q1781923":{"pageid":1792665,"ns":120,"title":"Item:Q1781923","lastrevid":71248149,"modified":"2026-04-13T20:58:28Z","type":"item","id":"Q1781923","labels":{"en":{"language":"en","value":"Topology and ambiguity in \\(\\omega\\)-context free languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2174590"}},"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":"Q1781923$DB6E0AB2-2C28-4C66-9EEA-89B41AD5C505","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"65ae94611e1db85d1713c5dc4e08a8dc8fd400f4","datavalue":{"value":{"text":"Topology and ambiguity in \\(\\omega\\)-context free languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1781923$97437E76-1DD4-47DF-B5AD-247F5951E90B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"725408659129ed05c5f1d34afc283b11940e1335","datavalue":{"value":"1080.68054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781923$C27C3D5A-E981-4868-A791-4B9115B3810C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"da5cec85976887ea974bbe2cdde3814e9335c077","datavalue":{"value":{"entity-type":"item","numeric-id":324244,"id":"Q324244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1781923$B26AC73C-542B-4DB4-93E4-74BDB726129F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ffe5cd000b9aef132c051c37fba47d5d9b5da5f2","datavalue":{"value":{"entity-type":"item","numeric-id":638868,"id":"Q638868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1781923$D930C0AE-C500-417F-80AF-6DCE090B66F9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c4f16ddc5cdb18d4f4fb3ee6d704d6609c3404ba","datavalue":{"value":{"entity-type":"item","numeric-id":223802,"id":"Q223802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1781923$82B980EA-9179-4231-8BAD-8FEFB8C42AE8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ce57d70a75dd4551033850269d3a862556d05764","datavalue":{"value":{"time":"+2005-06-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1781923$B0E25CBD-DAD6-4941-BB88-6A1FCC5DD6F6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9d2e28c54bb83b680a2583c022438641b7744fe2","datavalue":{"value":"https://projecteuclid.org/euclid.bbms/1074791327","type":"string"},"datatype":"url"},"type":"statement","id":"Q1781923$BADE5831-4EEE-4429-9851-3490E3F326E4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"88ac7fcb1342d91a1e860a3f3972c29d959c24ac","datavalue":{"value":"In this paper the connection between the topological complexity of an \\(\\omega\\)-context-free language (\\(\\omega\\)-CF laguage) and its degree of ambiguity is shown. The \\(\\omega\\)-CF languages are accepted by B\u00fcchi Pushdown Automata (BPDA), and the degree of ambiguity of a given infinite word is the number of different accepting runs in the automaton for this word. Using descriptive set theory it is proved that if \\(L(A)\\) is a non-Borel \\(\\omega\\)-CF language accepted by BPDA \\(A\\), then there exist \\(2^{\\aleph_0}\\) infinite words such that they have \\(2^{\\aleph_0}\\) accepting runs in \\(A\\), where \\(2^{\\aleph_0}\\) is the cardinality of the continuum. It follows that neither non-ambiguity nor inherent ambiguity are preserved by taking the adherence or the \\(\\delta\\)-limit of a finitary CF language. The adherence of the set \\(W\\) of finite words is the set of all infinite words such that the set prefixes of an infinite word is a subset of the set of prefixes of \\(W\\), and the \\(\\delta\\)-limit of \\(W\\) is a set of infinite words having infinitely many prefixes in \\(W\\). Also topology and ambiguity of infinitary rational relations is studied.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781923$3D180931-7CCA-465A-B246-61334CF041F0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9dce5c88da99cb4b1021e2cac25a18f2fa317715","datavalue":{"value":{"entity-type":"item","numeric-id":287018,"id":"Q287018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1781923$7E69997B-88D7-417B-9958-0F513401BD23","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781923$77EB4021-A442-48E4-9537-BE78100CA69F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781923$64CFAF2C-5C55-47B7-BC91-5923DB303FE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3fca415580115e1e0a74c69afb3a7d85b0c01d8d","datavalue":{"value":"03D55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781923$D961796E-AAB9-4D7C-8F9B-BAF52E633E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3636caf529c49b2a7d814c7a65de2b21aedf761","datavalue":{"value":"03E15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781923$E6004815-C92F-4382-AADC-A48520B5D9B2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cc5eab2689d7673ca5f44ececfae0e3761439194","datavalue":{"value":"2174590","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781923$48C8FA64-D5DF-4DBB-9D72-B73C8C531688","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44d2f2957b6a571bacf97ef6be5a6945b29311c7","datavalue":{"value":"context free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781923$5986A09C-2509-44D3-823F-244EF061C2DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91bf40d767c64624931b686e81b905c7b43bef72","datavalue":{"value":"infinite words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781923$5223FDF3-7A17-457A-99FB-01B695B49FAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6564d49a722a394780dffb896418fcaffbec2d6","datavalue":{"value":"infinitary rational relations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781923$BACA18B3-9F2C-447B-AE4E-8BBB15DD79CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dece2b67a16f221be015e3ceddb4de928543fdd9","datavalue":{"value":"ambiguity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781923$574ECC99-A023-4582-BA81-9911C933DA1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5673f420703540e5f595fdac2308b2a23244277b","datavalue":{"value":"topological properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781923$4EF2B8EB-4B87-4006-81B4-D5699A9A191F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af47dd0d79a1f58f2e4b3e8819f78e985cf685b3","datavalue":{"value":"Borel hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781923$2946E19D-31E0-4D85-AD7D-03303AA52442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3192df2a79c607156793bdbc30a42940a2e1f728","datavalue":{"value":"analytic sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781923$252653CA-3D91-473A-82FE-3BCD765D635D","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":"Q1781923$2A2352E7-884B-470A-AE3F-8FC164FCF90D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b17221d5b3766a82d6e2e685165ca769f18df567","datavalue":{"value":{"entity-type":"item","numeric-id":1399989,"id":"Q1399989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56248961272af148be779b25bd1bf4718b6c7d10","datavalue":{"value":{"amount":"+0.8782820701599121","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":"Q1781923$934C9CEB-4F80-4BCE-A131-9C76E2226725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b0ffce23132de5b0bf998ef8ca6086af52193eb","datavalue":{"value":{"entity-type":"item","numeric-id":5498741,"id":"Q5498741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50b7bdf1c18b043ecd5a1f99f2fe42e33cac9728","datavalue":{"value":{"amount":"+0.8641745448112488","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":"Q1781923$8B0BE26C-3474-4BA0-861F-5E4633599A52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8076c9bb2153f8795f4f21b56f32b9bb8905fa2","datavalue":{"value":{"entity-type":"item","numeric-id":1401165,"id":"Q1401165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a05d983d269eab20230890fbb0731a200b54f50","datavalue":{"value":{"amount":"+0.8354887366294861","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":"Q1781923$46B3FBC2-5B1C-46B7-A1D7-ADB2A6C2EFEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc6e97339341d5bf8487431958efea667343b38f","datavalue":{"value":{"entity-type":"item","numeric-id":5958141,"id":"Q5958141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68c1acc9667d4d6af40ba7cd25786a0b1d4db91e","datavalue":{"value":{"amount":"+0.8352568745613098","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":"Q1781923$66039A8A-5659-4AD5-BDC3-9193CE735876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9205a6358924edd63b5427106636684bd4d4383c","datavalue":{"value":{"entity-type":"item","numeric-id":3509076,"id":"Q3509076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68c1acc9667d4d6af40ba7cd25786a0b1d4db91e","datavalue":{"value":{"amount":"+0.8352568745613098","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":"Q1781923$1C097F79-5698-4731-A14A-854CD367BEDA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Topology and ambiguity in \\(\\omega\\)-context free languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Topology_and_ambiguity_in_%5C(%5Comega%5C)-context_free_languages"}}}}}