Vi betraktar problemet med att lära sig deterministiska till och med linjära språk från positiva exempel. Vi visar att för alla icke-negativa heltal k, klass LR(k) även linjära språk är inte lärbar från positiva exempel medan det finns en subklass som kallas US(k), som är en naturlig subklass av U(A) i stark mening, lärbar från positiva exempel. Vår inlärningsalgoritm identifierar denna underklass i gränsen med nästan linjär tid för att uppdatera gissningar. Som en följd av, i termer av även linjär grammatik, har vi en inlärningsalgoritm för k-reversibla språk som är mer effektiv än den som föreslås av Angluin.
Efter samma idé, deterministiska även linjär grammatik är polynomiskt identifierbara från positiva exempel endast REF.
Learning deterministic even linear languages from positive examples
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}