How to Invent Characterizable Inference Methods for Regular Languages
Abstract
We present a general framework for constructing characterizable inference algorithms for regular languages. This general approach is based on the fact, that certain families of non-trivial and infinite regular languages can be described with finite tuples of finite sets of strings (or trees). It follows from this property, that the methods are able to inductively learn in the limit from positive samples only. It is also shown that if the mapping from these presentations to languages is monotonic, and can be approximated in an acceptable way, then this approximation can be used to construct the presentation of the smallest language in the family containing a given sample. We show the applicability of this framework for both the familiar regular string languages and the regular tree languages.
Cite
Text
Knuutila. "How to Invent Characterizable Inference Methods for Regular Languages." International Conference on Algorithmic Learning Theory, 1993. doi:10.1007/3-540-57370-4_49Markdown
[Knuutila. "How to Invent Characterizable Inference Methods for Regular Languages." International Conference on Algorithmic Learning Theory, 1993.](https://mlanthology.org/alt/1993/knuutila1993alt-invent/) doi:10.1007/3-540-57370-4_49BibTeX
@inproceedings{knuutila1993alt-invent,
title = {{How to Invent Characterizable Inference Methods for Regular Languages}},
author = {Knuutila, Timo},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1993},
pages = {209-222},
doi = {10.1007/3-540-57370-4_49},
url = {https://mlanthology.org/alt/1993/knuutila1993alt-invent/}
}