Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries (Q5941371): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finding patterns common to a set of strings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Inductive inference of formal languages from positive data / rank
 
Normal rank
Property / cites work
 
Property / cites work: Queries and concept learning / rank
 
Normal rank
Property / cites work
 
Property / cites work: Avoidable patterns in strings of symbols / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the complexity of inductive inference / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3787511 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parallelism in random access machines / rank
 
Normal rank
Property / cites work
 
Property / cites work: Prudence and other conditions on formal language learning / rank
 
Normal rank
Property / cites work
 
Property / cites work: Language identification in the limit / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5592246 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4023519 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3335016 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4282558 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Inclusion is undecidable for pattern languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4013526 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on the two-variable pattern-finding problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial-time inference of arbitrary pattern languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Set-driven and rearrangement-independent learning of recursive languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Identification of pattern languages from examples and queries / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4763513 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4749224 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Inductive inference of unbounded unions of pattern languages from positive data / rank
 
Normal rank
Property / cites work
 
Property / cites work: A theory of the learnable / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ignoring data may be the only way to learn efficiently / rank
 
Normal rank
Property / cites work
 
Property / cites work: Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time / rank
 
Normal rank

Latest revision as of 19:25, 3 June 2024

scientific article; zbMATH DE number 1635559
Language Label Description Also known as
English
Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries
scientific article; zbMATH DE number 1635559

    Statements

    Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    20 August 2001
    0 references
    A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting non-empty strings for variables. We study the learnability of one-variable pattern languages in the limit with respect to the update time needed for computing a new single hypothesis and the expected total learning time taken until convergence to a correct hypothesis. Our results are as follows. First, we design a consistent and set-driven learner that, using the concept of descriptive patterns, achieves update time \(O(n^{2}\log n)\), where \(n\) is the size of the input sample. The best previously known algorithm for computing descriptive one-variable patterns requires time \(O(n^{4}\log n)\) [cf. \textit{D. Angluin}, J. Comput. Syst. Sci. 21, No. 1, 46-62 (1980; Zbl 0454.68108)]. Second, we give a parallel version of this algorithm that requires time \(O(\log n)\) and \(O(n^{3}/\log n)\) processors on an EREW-PRAM. Third, using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable patterns whose expected total learning time is \(O(\ell^{2}\log\ell)\) provided the sample strings are drawn from the target language according to a probability distribution with expected string length \(\ell\). The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Thus, we establish the first algorithm for learning one-variable pattern languages having an expected total learning time that provably differs from the update time by a constant factor only. Finally, we show how the algorithm for descriptive one-variable patterns can be used for learning one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language.
    0 references
    0 references
    inductive learning
    0 references
    one-variable pattern languages
    0 references
    average-case analysis
    0 references
    parallelization
    0 references