No label defined (Q4029602)

[For the entire collection see Zbl 0745.00057.] Denote the \(SM\) the family of languages generated by strictly monotone pure grammars (triples \((V,P,S)\) with \(V\) an alphabet, \(S \in V\), \(P \subseteq V^* \times V^*\) and for \((x,y) \in P\), \(1 \leq | x |< | y |)\). Using ideas from analytic linguistics, an algorithm is proposed for inferring grammars starting from samples of languages: given the set \(L_ k\) of strings of length at most \(k\), \(k \geq 1\), in some language \(L\), the algorithm produces a pure grammar \(G_ k\) such that \(L_ k \subseteq L(G_ k)\). It is proved that a language \(L\) is in family \(SM\) if and only if this algorithm converges in the sense that there is \(k_ 0\) such that \(L(G_ k)=L(G_{k_ 0})=L\), \(k \geq k_ 0\). The family \(SM\) is shown to include strictly the family of regular languages and to be incomparable with the family of context-free language. Two complexity measures for the above algorithm are considered (the smallest \(k_ 0\) as above and the longest interval of integers smaller than \(k_ 0\) for which the algorithm produces the same grammar); the last section discusses applications (in artificial intelligence, syntactic pattern recognition, developmental biology etc.).