Decision lists over regular patterns

The paper introduces the notion of decision lists over regular patterns. This formalism provides a strict extension of regular erasing pattern languages and of containment decision lists. Formal properties of the resulting language class, a subclass of the regular languages, are investigated. In particular, we show that decision lists over regular patterns have exactly the same expressive power as decision trees over regular patterns. Moreover, we study the learnability of the resulting language class within different formal settings including Gold's model of learning in the limit as well as Valiant's model of approximately correct learning.

Authors

• Steffen Lange
• Jochen Nessel

Keywords

No keywords are indexed for this paper.