pith. sign in

arxiv: 2511.12039 · v2 · pith:FRC3SDC3new · submitted 2025-11-15 · 💻 cs.FL

Positive Characteristic Sets for Relational Pattern Languages

S. Mahmoud Mousawi , Sandra Zilles This is my paper

Pith reviewed 2026-05-21 19:37 UTC · model grok-4.3

classification 💻 cs.FL
keywords positive characteristic setsrelational pattern languageslearning from positive examplesformal language learninginductive inferencestring processing
0
0 comments X

The pith

Positive characteristic sets of polynomial size exist for relational pattern languages, enabling efficient learning from positive examples.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces positive characteristic sets consisting only of positive examples for identifying an unknown target language within a reference class of languages. For relational pattern languages, these sets satisfy conditions that let a learning algorithm identify the target using positive data alone. This matters for applications in string processing where negative examples are unavailable or hard to obtain. The work examines the existence and utility of such sets specifically for the relational pattern language classes under study.

Core claim

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. A polynomial-size positive characteristic set for a language L with respect to a reference class allows a learning algorithm to efficiently identify L within the class using only positive examples.

What carries the argument

The positive characteristic set: a collection of (word, positive label) pairs that meets identification conditions allowing efficient recovery of the target language from positive data alone.

Load-bearing premise

That polynomial-size positive characteristic sets exist for the relational pattern language classes and satisfy the stated conditions for identification by a learning algorithm.

What would settle it

A relational pattern language class for which no polynomial-size set of only positive examples permits a learner to identify the target within the class.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper introduces positive characteristic sets—subsets consisting solely of positive examples—for classes of relational pattern languages. It constructs such sets explicitly, establishes that they have polynomial size in the relevant parameters (such as pattern length and number of variables), and proves that they suffice for efficient identification of the target language within the reference class from positive data alone, relying on the finite basis property of the pattern class.

Significance. If the constructions and bounds hold, this advances grammatical inference by addressing learning from positive examples only, a setting of practical relevance for string processing applications where negative data may be unavailable or costly. The explicit polynomial-size constructions and avoidance of fitted parameters or hidden assumptions provide concrete, verifiable guarantees that strengthen the result beyond mere existence claims.

minor comments (3)
  1. The abstract states that the sets are of 'polynomial size in the relevant parameters' but does not name those parameters (e.g., pattern length, number of relations); adding this would improve immediate readability.
  2. Section 2 (preliminaries): an early concrete example of a relational pattern and its positive characteristic set would help distinguish the relational case from standard pattern languages and clarify the finite basis property usage.
  3. In the size analysis (around the main theorem), the enumeration over substitutions is described at a high level; expanding the bound derivation with an explicit inequality relating substitution length to pattern size would aid verification.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive assessment of our manuscript on positive characteristic sets for relational pattern languages. We appreciate the recognition of the explicit polynomial-size constructions and their relevance to learning from positive examples only. The recommendation for minor revision is noted, and we will address any specific suggestions in the revised version.

Circularity Check

0 steps flagged

No significant circularity; explicit constructions from definitions

full rationale

The paper introduces positive characteristic sets via definition and then constructs them explicitly for relational pattern languages by leveraging the finite basis property of the class, yielding polynomial-size sets that satisfy the stated identification conditions from positive examples alone. These steps are direct constructive proofs grounded in the structural properties of the pattern languages and the reference class, without any reduction to fitted parameters, self-referential definitions, or load-bearing self-citations that would make the central claims equivalent to their inputs by construction. The derivation chain remains self-contained and independent.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only abstract available; no free parameters, axioms, or invented entities can be identified from the provided text.

pith-pipeline@v0.9.0 · 5642 in / 881 out tokens · 85385 ms · 2026-05-21T19:37:19.839209+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages · 1 internal anchor

  1. [1]

    New Generation Comput.11, 361–375 (1993)

    Arikawa, S., Miyano, S., Shinohara, A., Kuhara, S., Mukouchi, Y., Shinohara, T.: 26 A machine discovery from amino acid sequences by decision trees over regular patterns. New Generation Comput.11, 361–375 (1993)

    work page 1993

  2. [2]

    ACM Trans

    Nix, R.P.: Editing by example. ACM Trans. Program. Lang. Syst.7, 600–621 (1985)

    work page 1985

  3. [3]

    In: SPIRE, pp

    Clifford, R., Harrow, A.W., Popa, A., Sach, B.: Generalised matching. In: SPIRE, pp. 295–301 (2009)

    work page 2009

  4. [4]

    Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21, 46–62 (1980)

    work page 1980

  5. [5]

    In: Proc

    Shinohara, T.: Polynomial time inference of extended regular pattern languages. In: Proc. RIMS Symposia on Software Science and Engineering, pp. 115–127 (1982)

    work page 1982

  6. [6]

    In: ALT, pp

    Geilke, M., Zilles, S.: Learning relational patterns. In: ALT, pp. 84–98 (2011)

    work page 2011

  7. [7]

    In: ALT, pp

    Holte, R.C., Mousawi, S.M., Zilles, S.: Distinguishing relational pattern languages with a small number of short strings. In: ALT, pp. 498–514 (2022)

    work page 2022

  8. [8]

    An Overview of Machine Teaching

    Zhu, X., Singla, A., Zilles, S., Rafferty, A.N.: An overview of machine teaching. ArXivabs/1801.05927(2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  9. [9]

    Higuera, C.: Characteristic sets for polynomial grammatical inference. Mach. Learn.27(2), 125–138 (1997)

    work page 1997

  10. [10]

    Gold, E.M.: Language identification in the limit. Inform. Control10, 447–474 (1967)

    work page 1967

  11. [11]

    Angluin, D.: Inductive inference of formal languages from positive data. Inform. Control45, 117–135 (1980)

    work page 1980

  12. [12]

    In: SOFSEM, pp

    Mousawi, S..M., Zilles, S.: Positive characteristic sets for relational pattern languages. In: SOFSEM, pp. 398–412 (2024)

    work page 2024

  13. [13]

    Lange, S., Zeugmann, T., Zilles, S.: Learning indexed families of recursive lan- guages from positive data: A survey. Theor. Comput. Sci.397(1-3), 194–232 (2008)

    work page 2008

  14. [14]

    Fallat, S., Kirkpatrick, D., Simon, H.U., Soltani, A., Zilles, S.: On batch teaching without collusion. J. Mach. Learn. Res.24, 1–33 (2023)

    work page 2023

  15. [15]

    Jiang, T., Salomaa, A., Salomaa, K., Yu, S.: Decision problems for patterns. J. Comput. Syst. Sci.50(1), 53–63 (1995)

    work page 1995

  16. [16]

    In: ALT, pp

    Reidenbach, D.: A negative result on inductive inference of extended pattern languages. In: ALT, pp. 308–320 (2002) 27 Appendix A Proofs Omitted From the Main Body of the Paper Lemma 8.LetΣ ={a, b}anda̸=b. Letp=⃗ x 1an1 bn2⃗ x2an3⃗ x3 andp ′ = ⃗ x′ 1an1⃗ x′ 2bn2 an3⃗ x′ 3, wheren 1, n2, n3 ∈N,⃗ x1, ⃗ x′ 1, ⃗ x3, ⃗ x′ 3 ∈X ∗ and⃗ x2, ⃗ x′ 2 ∈X +. LetR andR...

    work page 2002

  17. [17]

    Thenpandp ′ contain telltale conjugates that are not adjacent to terminal symbols, which contradicts the premise of the lemma

    ω′ i+1 = ωi+1 =εandk 1 = 1. Thenpandp ′ contain telltale conjugates that are not adjacent to terminal symbols, which contradicts the premise of the lemma

    work page

  18. [18]

    ω′ i+1 = ωi+1 =εandk 1 ≥2. Then anR-substitution replacing the last variable in⃗ xi+1 byba, its group members byaa, and other variables byεgenerates a word frompthat cannot be generated from (p ′, R′), so that (⋆) holds

    work page

  19. [19]

    Consider the following cases: (a) ωi+1 =ε

    ω′ i+1 starts witha. Consider the following cases: (a) ωi+1 =ε. Thenpandp ′ contain telltale conjugates that are not adjacent to terminal symbols; a contradiction. (b) ω′ i+1 starts withaawhile ωi+1 =a. Then anR-substitution replacing some variable in⃗ xi+1 (and its group members) byb, and other variables byε, generates a word frompthat cannot be generate...

    work page

  20. [20]

    Ifk 3 ≥2 andk ′ 4 ≥2, then we obtain (⋆) with anR-substitution mapping the first variable in⃗ xi+2 toba, all its group members toaa, and all other variables toε

    work page

  21. [21]

    In this case, the proof of the lemma proceeds iteratively, replacingpandp ′ as follows: p=⃗ x1⃗ x2

    Ifk 3 = 1 ork ′ 4 = 1, then we will focus onω i+2 andω ′ i+2. In this case, the proof of the lemma proceeds iteratively, replacingpandp ′ as follows: p=⃗ x1⃗ x2 . . . ⃗ xi+2 ωi+2 . . . ⃗ xn ωn⃗ xn+1 , p′ =⃗ x′ 1⃗ x′ 2 . . . ⃗ x′ i+2 ω′ i+2 . . . ⃗ x′ n ω′ n .⃗ x′ n+1 . It remains to considerk ′ 4 = 0, which results in ωi =a k1 , ω i+1 =ba k3 ωi+1 , ω′ i =...

    work page

  22. [22]

    With ωi+1 ̸= ω′ i+1, this implies ω′ i+1 ̸=ε

    ωi+1 =ε. With ωi+1 ̸= ω′ i+1, this implies ω′ i+1 ̸=ε. Moreover,⃗ x i+2 ̸=ε, since otherwisei+ 1 =nand thusω 1 . . . ωn ̸=ω ′ 1 . . . ω′ n′. Thusω ′ i+1 begins witha k3+1. In this case, (⋆) is witnessed by anR-substitution that replaces some variable in ⃗ xi+2 (and all its group members) bybwhile erasing all other variables

    work page

  23. [23]

    If ω′ i+1 does not begin witha t then there is some 0≤t ′ < tsuch that ω′ i+1 =a t′

    ωi+1 ̸=ε, i.e., there is somet≥1 such that ωi+1 ∈ {a t} ∪ {a tbΣ∗}. If ω′ i+1 does not begin witha t then there is some 0≤t ′ < tsuch that ω′ i+1 =a t′ . Note that then⃗ x′ i+2 ̸=ε. Now anR ′-substitution that replaces a variable in⃗ x′ i+2 (and all its group members) withb, while erasing all other variables, generates a word fromp ′ that cannot be genera...

    work page