Grammatical inference of directed acyclic graph languages with polynomial time complexity

DOI10.1016/j.jcss.2017.12.002zbMath1390.68362OpenAlexW2777464707WikidataQ58201096 ScholiaQ58201096MaRDI QIDQ1747486

Damián López, Jorge Calera-Rubio, Antonio-Javier Gallego

Publication date: 8 May 2018

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

Full work available at URL: http://hdl.handle.net/10251/136876

zbMATH Keywords

grammatical inferencegraph languagesgraph automata\(k\)-testable languages

Mathematics Subject Classification ID

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

Uses Software

• IgTM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Learning context-free grammars from structural data in polynomial time
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Efficient learning of context-free grammars from positive structural examples
• On the learnability and usage of acyclic probabilistic finite automata
• Nondeterminism versus determinism of finite automata over directed acyclic graphs
• Finite graph automata for linear and boundary graph languages
• Polynomial-time identification of very simple grammars from positive data.
• Learning context-free grammars using tabular representations
• Smoothing and compression with stochastic \(k\)-testable tree languages
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Learning Context-Sensitive Languages from Linear Structural Information
• Learning Node Label Controlled Graph Grammars (Extended Abstract)
• Estimating Graph Parameters Using Graph Grammars
• A Polynomial Algorithm for the Inference of Context Free Languages
• Incremental Learning of Context Free Grammars by Bridging Rule Generation and Search for Semi-optimum Rule Sets
• Protein Motif Prediction by Grammatical Inference
• Automata on Directed Graphs: Edge Versus Vertex Marking
• Handbook of Graph Grammars and Computing by Graph Transformation
• Algebraic decision procedures for local testability
• Structural, Syntactic, and Statistical Pattern Recognition
• Language identification in the limit
• Stochastic inference of regular tree languages