Results 11 to 20 of about 170,686 (340)
On Müller context-free grammars
Theoretical Computer Science, 2011 AbstractWe define context-free grammars with Müller acceptance condition that generate languages of countable words. We establish several elementary properties of the class of Müller context-free languages including closure properties and others. We show that every Müller context-free grammar can be transformed into a normal form grammar in polynomial ...
Zoltán Ésik, Szabolcs Iván
openalex +4 more sources
RNA Pseudoknotted Structure Prediction Using Stochastic Multiple Context-Free Grammar
Information and Media Technologies, 2006 Many attempts have so far been made at modeling RNA secondary structure by formal grammars. In a grammatical approach, secondary structure prediction can be viewed as parsing problem.
Yuki Kato, Hiroyuki Seki, Tadao Kasami
openalex +3 more sources
Learning of Structurally Unambiguous Probabilistic Grammars [PDF]
Logical Methods in Computer Science, 2023 The problem of identifying a probabilistic context free grammar has two aspects: the first is determining the grammar's topology (the rules of the grammar) and the second is estimating probabilistic weights for each rule.
Dana Fisman +2 more
doaj +1 more source
PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols [PDF]
North American Chapter of the Association for Computational Linguistics, 2021 Probabilistic context-free grammars (PCFGs) with neural parameterization have been shown to be effective in unsupervised phrase-structure grammar induction.
Songlin Yang, Yanpeng Zhao, Kewei Tu
semanticscholar +1 more source
Split-Based Algorithm for Weighted Context-Free Grammar Induction
Applied Sciences, 2021 The split-based method in a weighted context-free grammar (WCFG) induction was formalised and verified on a comprehensive set of context-free languages. WCFG is learned using a novel grammatical inference method. The proposed method learns WCFG from both
Mateusz Gabor +2 more
doaj +1 more source
Learning Cover Context-Free Grammars from Structural Data [PDF]
Scientific Annals of Computer Science, 2014 We consider the problem of learning an unknown context-free gram- mar from its structural descriptions with depth at most ℓ. The structural descriptions of the context-free grammar are its unlabelled derivation trees. The goal is to learn a cover context-
M. Marin, G. Istrate
doaj +1 more source
Compound Probabilistic Context-Free Grammars for Grammar Induction [PDF]
Annual Meeting of the Association for Computational Linguistics, 2019 We study a formalization of the grammar induction problem that models sentences as being generated by a compound probabilistic context free grammar. In contrast to traditional formulations which learn a single stochastic grammar, our context-free rule ...
Yoon Kim, Chris Dyer, Alexander M. Rush
semanticscholar +1 more source
Undecidable problems concerning densities of languages [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 In this paper we prove that the question whether a language presented by a context free grammar has density, is undecidable. Moreover we show that there is no algorithm which, given two unambiguous context free grammars on input, decides whether the ...
Jakub Kozik
doaj +1 more source
Mathematics, 2022 The limitations of traditional parsing architecture are well known. Even when paired with parsing methods that accept all context-free grammars (CFGs), the resulting combination for any given CFG accepts only a limited subset of corresponding character ...
Žiga Leber +3 more
doaj +1 more source
A Context-Free Grammar Associated with Fibonacci and Lucas Sequences
Journal of Mathematics, 2023 We introduce a context-free grammar G=s⟶s+d,d⟶s to generate Fibonacci and Lucas sequences. By applying the grammar G, we give a grammatical proof of the Binet formula.
Harold Ruilong Yang
doaj +1 more source