Rapid construction of algebraic axioms from samples (Q1179710)

The authors consider the problem of finding a correct rule of generation of a given sequence of elements of an enumerable domain set \(\mathcal N\). The idea is based on finding separate local regularities in a given sample of the sequence. Such local regularities can be described by algebraic axioms which are equalities of two terms. The basic question now is: can such axioms be found sufficiently fast, i.e. without an exhaustive search? A positive answer (in a sense) is given. An algebra \(A\) of finite signature \(\Sigma\) over \(\mathcal N\) is considered. A sample of \(A\) is a finite set \(P\) of elementary equations of \(A\). \({\mathcal N}_ p\) denotes the domain of \(P\). Given \(\langle a_ 1,\ldots,a_ k\rangle\in{\mathcal N}^ k_ P\), \(a_ i\neq a_ j\) if \(i\neq j\), and \(b\in{\mathcal N}^ k_ P\), by \(A_{P,(\langle a_ 1,\ldots,a_ k\rangle,b),l}\) is denoted the set of all open terms which satisfy the pair \((\langle a_ 1,\ldots,a_ k\rangle,b)\) in \(P\) and which have level no more than \(l\), \(l>0\) being a natural number. The authors obtain then the following two main results: {(1) } (Theorem 1) There exists an algorithm which enumerates all axioms which satisfy a given pair \((\langle a_ 1,\ldots,a_ k\rangle,b)\); these axioms are of the form \(t_ i=t_ j\) where \(t_ i,t_ j\in A_{P,(\langle a_ 1,\ldots,a_ k\rangle,b),l}\). {(2) } (Theorem 2) Common regularities can be enumerated quite fast, i.e. without enumerating all regularities of all considered pairs.