Lecture Notes in Computer Science, 2002, Volume 2533/2002, 308-320, DOI: 10.1007/3-540-36169-3_25

A Negative Result on Inductive Inference of Extended Pattern Languages

Daniel Reidenbach

View Related Documents

Abstract

The question of learnability of the class of extended pattern languages is considered to be one of the eldest and outstanding open problems in inductive inference of formal languages. This paper provides an appropriate answer presenting a subclass - the terminal-free extended pattern languages - that is not learnable in the limit. In order to achieve this result we will have to limit the respective alphabet of terminal symbols to exactly two letters. In addition we will focus on the impact of ambiguity of pattern languages on inductive inference of terminal-free extended pattern languages. The conventional view on nondeterminism in patterns inspired by formal language theory is transformed into an approach that meets the requirements of inductive inference. These studies will lead to some useful learnability criteria for classes of terminal-free extended pattern languages.

Fulltext Preview

Image of the first page of the fulltext document