Finite thickness




In formal language theory, in particular in algorithmic learning theory, a class C of languages has finite thickness if every string is contained in at most finitely many languages in C. This condition was introduced by Dana Angluin as a sufficient condition for C being identifiable in the limit.
[1]



The related notion of M-finite thickness


Given a language L and an indexed class C = { L1, L2, L3, ... } of languages, a member language Lj ∈ C is called a minimal concept of L within C if L ⊆ Lj, but not L ⊊ Li ⊆ Lj for any Li ∈ C.[2]
The class C is said to satisfy the MEF-condition if every finite subset D of a member language Li ∈ C has a minimal concept Lj ⊆ Li. Symmetrically, C is said to satisfy the MFF-condition if every nonempty finite set D has at most finitely many minimal concepts in C. Finally, C is said to have M-finite thickness if it satisfies both the MEF- and the MFF-condition.
[3]


Finite thickness implies M-finite thickness.[4] However, there are classes that are of M-finite thickness but not of finite thickness (for example, any class of languages C = { L1, L2, L3, ... } such that L1 ⊆ L2 ⊆ L3 ⊆ ...).



References





  1. ^ Dana Angluin (1980). "Inductive Inference of Formal Languages from Positive Data" (PDF). Information and Control. 45 (2): 117–135. doi:10.1016/s0019-9958(80)90285-5..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em} (citeseer.ist.psu.edu); here: Condition 3, p.123 mid. Angluin's original requirement (every non-empty string set be contained in at most finitely many languages) is equivalent.


  2. ^ Andris Ambainis; Sanjay Jain; Arun Sharma (1997). "Ordinal mind change complexity of language identification". Computational Learning Theory (PDF). LNCS. 1208. Springer. pp. 301–315.; here: Definition 25


  3. ^ Ambainis et al. 1997, Definition 26


  4. ^ Ambainis et al. 1997, Corollary 29











-

Popular posts from this blog

Eastern Orthodox Church

Image
Not to be confused with Oriental Orthodoxy, Eastern Christianity, or Eastern Catholic Churches. "Eastern Orthodoxy", "Orthodox Church", "Orthodox Catholic Church", and "Orthodox Christian Church" redirect here. For other uses, see Orthodox (disambiguation). This article may be too long to read and navigate comfortably . The readable prose size is 132 kilobytes. Please consider splitting content into sub-articles, condensing it, or adding or removing subheadings. ( January 2018 ) Part of a series on the Eastern Orthodox Church Mosaic of Christ Pantocrator, Hagia Sophia Overview Structure Theology (History of theology) Liturgy Church history Holy Mysteries View of salvation View of Mary View of icons Background Crucifixion / Resurrection / Ascension of Jesus Christianity Christian Church Apostolic succession Four Marks of the Church Orthodoxy Organization Autocephaly Patriarchate ...
Read more

Zagreb

Image
This article is about the Croatian capital city. For other uses, see Zagreb (disambiguation). City in City of Zagreb, Croatia Zagreb City Grad Zagreb City of Zagreb Clockwise, from top: St. Mark's Square, Croatian State Archives, Zagreb Tram, Art Pavilion, Cibona & HOTO towers and Croatian National Theatre. Flag Coat of arms Zagreb Location of Zagreb in Croatia Show map of Croatia Zagreb Zagreb (Europe) Show map of Europe Coordinates: 45°49′N 15°59′E  /  45.817°N 15.983°E  / 45.817; 15.983 Coordinates: 45°49′N 15°59′E  /  45.817°N 15.983°E  / 45.817; 15.983 Country   Croatia County City of Zagreb RC diocese 1094 Free royal city 1242 Unified 1850 Subdivisions 17 city districts 218 local committees (70 settlements) Government  • Type Mayor-Council  • Mayor Milan Bandić (BM 365)  • City Assembly 51 members BM 365, ZL, NS-R (14) SDP, GLAS, HNS, HSS, NH-PS (13) ...
Read more

Understanding the information contained in the Deep Space Network XML data?

Image
up vote 1 down vote favorite NASA's Deep Space Network activity can be viewed conveniently at https://eyes.nasa.gov/dsn/dsn.html but if you would like data in a more raw XML form, it can be accessed as described in this answer Below is a small Python script that reads the XML into a list of dictionaries, and saves it to disk as a JSON. The dictionaries are organized at the higher level by dish, then by spacecraft per dish. Question: What are the most-likely meanings of all the data field contained in the Deep Space Network XML data? This is the example url from the other answer, used in the script below: https://eyes.nasa.gov/dsn/data/1365107113.xml def dictify(r,root=True): # https://stackoverflow.com/questions/2148119/how-to-convert-an-xml-string-to-a-dictionary-in-python/30923963#30923963 if root: ret...
Read more