Inferring descriptive generalisations of formal languages

DOI10.1016/J.JCSS.2012.10.001MaRDI QIDQ355503zbMATH OpenOpenAlexFDO

Authors Dominik D. Freydenberger, Daniel Reidenbach

Publication date 24 July 2013

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2012.10.001

zbMATH Keywords

inductive inferencepattern languagesdescriptive generalisationdescriptive patternsupper approximate identification from positive data

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational learning theory (68Q32)

Recommendations

• Discontinuities in pattern inference
• Polynomial-time inference of arbitrary pattern languages
• Inductive inference of languages from samplings
• scientific article; zbMATH DE number 791077
• Optimal Language Learning

Cites work

• scientific article; zbMATH DE number 2077180 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3806956 (Why is no real title available?)
• scientific article; zbMATH DE number 1414302 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• A non-learnable class of E-pattern languages
• An average-case optimal one-variable pattern language learner
• Bad news on decision problems for patterns
• Decision problems for patterns
• Developments from enquiries into the learnability of the pattern languages from positive data
• Discontinuities in pattern inference
• Existence and nonexistence of descriptive patterns
• Fast learning of restricted regular expressions and dtds
• Finding a homomorphism between two words is NP-complete
• Finding patterns common to a set of strings
• Identification of function distinguishable languages.
• Ignoring data may be the only way to learn efficiently
• Inductive inference of formal languages from positive data
• Inferring descriptive generalisations of formal languages
• Language identification in the limit
• Learning and extending sublanguages
• Learning approximately regular languages with reversible languages
• Learning in the presence of inaccurate information
• Learning indexed families of recursive languages from positive data: A survey
• Morphically primitive words
• Pattern languages with and without erasing
• Polynomial-time algorithm for fixed points of nontrivial morphisms
• Polynomial-time inference of arbitrary pattern languages
• Uncountable automatic classes and learning

Cited in

(9)

• Fast learning of restricted regular expressions and dtds
• Representing structural language features in formal meta-languages
• scientific article; zbMATH DE number 5545149 (Why is no real title available?)
• Toward complete programming language descriptions that are both formal and understandable
• Implications between generative properties and analytical properties of formal languages
• scientific article; zbMATH DE number 7278096 (Why is no real title available?)
• Distinguishing pattern languages with membership examples
• Inferring descriptive generalisations of formal languages
• Revisiting Shinohara's algorithm for computing descriptive patterns

This page was built for publication: Inferring descriptive generalisations of formal languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q355503)