Detta dokument handlar om en subklass av enkla deterministiska grammatiker, som kallas mycket enkla grammatiker, och studerar problemet med att identifiera subklassen i gränsen från positiva data. Klassen av mycket enkla språk utgör en lämplig underklass av enkla deterministiska språk och är ojämförlig med klassen av vanliga språk. Denna klass av språk är också känd som klassen av vänster Szilard språk av kontextfri grammatik. Efter att ha tillhandahållit vissa egenskaper hos mycket enkla språk, visar vi att klassen av mycket enkla grammatiker är polynom-tid identifierbar i gränsen från positiva data i följande mening. Det vill säga, vi visar att det finns en algoritm som, med tanke på ett mål mycket enkel grammatik G * över alfabetet, identifierar en mycket enkel grammatik G motsvarande G * i gränsen från positiva data, som uppfyller egenskapen att tiden för uppdatering av en gissning begränsas av O(m), och det totala antalet förutsägelser fel som gjorts av algoritmen begränsas av O(n), där n är storleken på G * ; m = Max{N  på + 1 ;  och N är den totala längden av alla positiva data som tillhandahålls.
Detta är den första bevisligen korrekta och effektiva grammatiska inferensalgoritmen för en språkligt intressant klass av kontextfri grammatik (men se till exempel REF på klassen av mycket enkel grammatik).
Polynomial-time identification of very simple grammars from positive data
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}