Positive Characteristic Sets for Relational Pattern Languages
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913135372271616 |
|---|---|
| author | Mousawi, S. Mahmoud Zilles, Sandra |
| author_facet | Mousawi, S. Mahmoud Zilles, Sandra |
| contents | In the context of learning formal languages, data about an unknown target language L is given in terms of a set of (word,label) pairs, where a binary label indicates whether or not the given word belongs to L. A (polynomial-size) characteristic set for L, with respect to a reference class L of languages, is a set of such pairs that satisfies certain conditions allowing a learning algorithm to (efficiently) identify L within L. In this paper, we introduce the notion of positive characteristic set, referring to characteristic sets of only positive examples. These are of importance in the context of learning from positive examples only. We study this notion for classes of relational pattern languages, which are of relevance to various applications in string processing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_12039 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Positive Characteristic Sets for Relational Pattern Languages Mousawi, S. Mahmoud Zilles, Sandra Formal Languages and Automata Theory In the context of learning formal languages, data about an unknown target language L is given in terms of a set of (word,label) pairs, where a binary label indicates whether or not the given word belongs to L. A (polynomial-size) characteristic set for L, with respect to a reference class L of languages, is a set of such pairs that satisfies certain conditions allowing a learning algorithm to (efficiently) identify L within L. In this paper, we introduce the notion of positive characteristic set, referring to characteristic sets of only positive examples. These are of importance in the context of learning from positive examples only. We study this notion for classes of relational pattern languages, which are of relevance to various applications in string processing. |
| title | Positive Characteristic Sets for Relational Pattern Languages |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2511.12039 |