{"entities":{"Q2431428":{"pageid":2442171,"ns":120,"title":"Item:Q2431428","lastrevid":51227390,"modified":"2026-01-17T08:25:13Z","type":"item","id":"Q2431428","labels":{"en":{"language":"en","value":"Uncountable automatic classes and learning"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5878097"}},"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":"Q2431428$27CE33F3-1ED7-4F00-9857-4C0912E9F07F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"92a2e53a309825463bffd367b32e422bbae92a83","datavalue":{"value":{"text":"Uncountable automatic classes and learning","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2431428$C140D65E-D4EC-464C-969F-BE9E82660D9F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"61e6e9a5f3e63bf3d4bdcffd0d0ca379a63be624","datavalue":{"value":"1222.68108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2431428$2F33B497-8BBA-4E90-9999-0ACC2B67A3DF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce7fbe956cf60c7c3ae673639c76733e0c2b340b","datavalue":{"value":{"entity-type":"item","numeric-id":197705,"id":"Q197705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$8DBED198-25F3-4ABD-9A75-8E24AA49EF75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c643d8b00db1cefe28fb09fb978ce4cb66f86aab","datavalue":{"value":{"entity-type":"item","numeric-id":1757848,"id":"Q1757848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$3BE45C93-8100-4C42-B7E9-4817F0E7453E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05f15d010c207ee596a2b36d0f61cf07430e5ece","datavalue":{"value":{"entity-type":"item","numeric-id":387120,"id":"Q387120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$A7297ACA-4D78-4683-B1EE-15BA25F69464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a56bc7b07f95b5885e3133c205b9456af5cfa030","datavalue":{"value":{"entity-type":"item","numeric-id":324251,"id":"Q324251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$DB466B87-F747-4D4D-BA03-3EDFA57ABF1C","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":"Q2431428$6DD8BAA1-C497-4882-AF95-AFC0A9FC3925","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ee1fd201af1e69b1d6b7cde2450cc5aa32a34627","datavalue":{"value":{"time":"+2011-04-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2431428$AAC9A519-80F4-438A-BF5E-822408B7D9F5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8cb49f1f73cbf58b8355df044fc9087d3780322b","datavalue":{"value":"In this paper the authors consider uncountable classes recognizable by \\(\\omega \\)-automata and investigate suitable learning paradigms for them. In particular, the counterparts of explanatory, vacillatory and behaviourally correct learning are introduced for this setting. Here the learner reads in parallel the data of a text for a language \\(L\\) from the class plus an \\(\\omega \\)-index \\(\\alpha \\) and outputs a sequence of \\(\\omega \\)-automata such that all but finitely many of these \\(\\omega \\)-automata accept the index \\(\\alpha \\) if and only if \\(\\alpha \\) is an index for \\(L\\).  It is shown that any class is behaviourally correct learnable if and only if it satisfies Angluin's tell-tale condition. On the one hand, every class satisfying Angluin's tell-tale condition is vacillatorily learnable in every indexing; on the other hand, there is a fixed class such that the level of the class in the hierarchy of vacillatory learning depends on the indexing of the class chosen.  The authors also consider a notion of blind learning. They show that a class is blind explanatorily (vacillatorily) learnable if and only if it satisfies Angluin's tell-tale condition and is countable. For behaviourally correct learning, there is no difference between the blind and non-blind version.  This work establishes a bridge between the theory of \\(\\omega \\)-automata and inductive inference (learning theory).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2431428$081C7953-BDC6-4530-8318-1C59A565273F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d752cb0ef563962b57095a8fe1381c36568051cd","datavalue":{"value":{"entity-type":"item","numeric-id":189517,"id":"Q189517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$76423293-F45C-4B27-9CD8-7DF6DB862497","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2431428$AAE971EC-6FA7-4476-BA68-EEE1171E0CB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c189c45b466f89dd188bd061df8c45f23f05da60","datavalue":{"value":"68Q32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2431428$E14E8191-0BB5-4629-8C1F-5937220B9F6B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"28b6d355c7bc511d6d3007e03e6917d21c7ea2ea","datavalue":{"value":"5878097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2431428$6370191F-B7EA-44D6-8E45-296166522F8D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dffde7808791c6e817a936696e48e18f4e8e1a16","datavalue":{"value":"uncountable classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2431428$B78B3A44-52E5-4E02-9B7C-56C1DF7E4BB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0be3912121ad79b9bb968c84460a2f4bde143ee3","datavalue":{"value":"automatic classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2431428$6B7530E9-6472-4837-B8EE-50860BA4E7F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1bca5b8f8493e57969b551637f12770d6fc436fb","datavalue":{"value":"learning theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2431428$529F6076-16DE-4A96-B8AD-80E17E6DBA6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df2db52a7243887f734f3533f390b79d7d369328","datavalue":{"value":"inductive inference","type":"string"},"datatype":"string"},"type":"statement","id":"Q2431428$2E263635-1B8F-4683-ACEE-A003FD3A8CD9","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":"Q2431428$4FB25EA9-F65C-40FA-AAF5-35FB914D883B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"98e056c199938924d705f7dbd3a7b3f9976d4eec","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2010.12.057","type":"string"},"datatype":"url"},"type":"statement","id":"Q2431428$52567123-91F5-438F-A72F-C2901038D179","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9d9133320d98a2da4ff2e0a71afcbd13af3a4af4","datavalue":{"value":"W2104868629","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2431428$9C5B66CC-9A66-4341-8C72-B61987509D74","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b40c59feb183e6f32a8e2fcf3769d2018e89bfa","datavalue":{"value":{"entity-type":"item","numeric-id":3910029,"id":"Q3910029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$19072B39-0F8D-45D5-B311-4FF31478F15C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751b61b5dbe828d0db5885461ea9cc6b65fc1e82","datavalue":{"value":{"entity-type":"item","numeric-id":4910735,"id":"Q4910735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$C1B6C75D-CCB5-4A7E-B982-785C5D0AB357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac6e2f28c5e39cfecc9d8cb690766cf09c1b2d7b","datavalue":{"value":{"entity-type":"item","numeric-id":1764419,"id":"Q1764419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$A19A4C3B-9C2A-4D5F-BFA8-713620858A37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"465c44674a94414cb55e7dc8cbdf974e7462af9b","datavalue":{"value":{"entity-type":"item","numeric-id":3287248,"id":"Q3287248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$DCCE4ED8-4B16-444D-8280-DE2D8D85F542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06c411f40bd3fed70a734570dda325013084ac01","datavalue":{"value":{"entity-type":"item","numeric-id":5525343,"id":"Q5525343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$2FDAAC0B-6D6F-414F-9A5A-FD9582F6300D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"139667734827b66c379e9281cd255c3bf54dad4c","datavalue":{"value":{"entity-type":"item","numeric-id":4268851,"id":"Q4268851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$EC32D813-B70C-4B36-8173-E2C2EEB521DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fac60edc46b96d391fd19f103e4a89f46a0a07b","datavalue":{"value":{"entity-type":"item","numeric-id":5674988,"id":"Q5674988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$D827F63E-97B1-4828-A7E3-0D93AD61D4DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a8b266f8abd0c0539db9d64a02d59707dd6f1e3","datavalue":{"value":{"entity-type":"item","numeric-id":3564874,"id":"Q3564874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$984F2F27-2AA6-4B39-98AB-07E2FAEB8CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4864c48578bc17fdc12bcc55684bf742669ee818","datavalue":{"value":{"entity-type":"item","numeric-id":5936849,"id":"Q5936849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$74306E37-CADB-47BD-9AE3-82D971561BC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66d39cb9a24edce54222b2b407d415352ff96982","datavalue":{"value":{"entity-type":"item","numeric-id":3396632,"id":"Q3396632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$806A15D1-640A-472E-84B4-0642AB2C2539","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39b59045408bdef02af3f5d84bef8023536de082","datavalue":{"value":{"entity-type":"item","numeric-id":3590920,"id":"Q3590920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2431428$6468E5AB-4406-4850-8EC5-7648B2A83A2F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ba681bd359310e6d4ba6937c602d27cb4248a4c0","datavalue":{"value":"10.1016/J.TCS.2010.12.057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2431428$89AF5F66-7615-44E0-8516-567DC7D36272","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d989c25a2f7f59f2b485586f98966b14af521332","datavalue":{"value":{"entity-type":"item","numeric-id":3648759,"id":"Q3648759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"168177c4b37b9415da81d7d25559d8bb29256d66","datavalue":{"value":{"amount":"+0.997554361820221","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":"Q2431428$32635BC6-D104-4D95-8E56-D859DDEDCB98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fef71c4f13e80b7c881e99e6efe4b6d0ae972a6","datavalue":{"value":{"entity-type":"item","numeric-id":1757849,"id":"Q1757849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de32b667b04cf0b4349ab2baf86ea25a55e7f3ee","datavalue":{"value":{"amount":"+0.8003385066986084","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":"Q2431428$1893B08E-38D1-435E-BEF3-270715DD378D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4c08acc4eda2af2725110c307ff9e227a90fe76","datavalue":{"value":{"entity-type":"item","numeric-id":3564874,"id":"Q3564874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8744490e43b6b5f60509d4d4dd71cdc9d168357d","datavalue":{"value":{"amount":"+0.7983890175819397","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":"Q2431428$08E76D58-6CA3-4672-B4F2-7F4AC2326AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ebe8370444c2175a7c5650a95156d4ca2228001","datavalue":{"value":{"entity-type":"item","numeric-id":1892893,"id":"Q1892893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59720475989c24b2a911b6d29f20963e956ac264","datavalue":{"value":{"amount":"+0.7792695164680481","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":"Q2431428$9E679A40-65EC-4D95-994A-D7D4704A4339","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d1cdd42e6235df0ab10af261b54e8e1a6f82e05","datavalue":{"value":{"entity-type":"item","numeric-id":5164178,"id":"Q5164178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59720475989c24b2a911b6d29f20963e956ac264","datavalue":{"value":{"amount":"+0.7792695164680481","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":"Q2431428$CA351035-B660-4DBC-8971-19DF3CCF3964","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2431428","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2431428"}}}}}