Results 11 to 20 of about 1,739 (253)
Grammar Compression with Probabilistic Context-Free Grammar [PDF]
2020 Data Compression Conference (DCC), 2020 We propose a new approach for universal lossless text compression, based on grammar compression. In the literature, a target string $T$ has been compressed as a context-free grammar $G$ in Chomsky normal form satisfying $L(G) = \{T\}$. Such a grammar is often called a \emph{straight-line program} (SLP).
Hiroaki Naganuma +4 more
openaire +2 more sources
Complexity of Problems of Commutative Grammars [PDF]
Logical Methods in Computer Science, 2015 We consider commutative regular and context-free grammars, or, in other words, Parikh images of regular and context-free languages. By using linear algebra and a branching analog of the classic Euler theorem, we show that, under an assumption that the ...
Eryk Kopczynski
doaj +1 more source
A Theoretical Foundation for Syntactico-Semantic Pattern Recognition
IEEE Access, 2021 Conventionally syntactic pattern recognition tasks have been driven by grammars defining a syntactic structure. Syntactic Pattern recognition tasks were primarily relying on the ability of parsing algorithms to recognize the patterns in the input data ...
Shrinivasan Patnaikuni, Sachin Gengaje
doaj +1 more source
Grammars with two-sided contexts [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 In a recent paper (M. Barash, A. Okhotin, "Defining contexts in context-free grammars", LATA 2012), the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being ...
Mikhail Barash, Alexander Okhotin
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
On Restricted Context-Free Grammars
Journal of Computer and System Sciences, 2010 The contribution investigates the generative power of several derivation-restricted context-free grammars. Many derivation restriction mechanisms for context-free grammars have already been studied in the literature, and the current contribution investigates a restriction on the non-terminals that allows/disallows the application of a production ...
Jürgen Dassow, Tomás Masopust
openaire +4 more sources
On Müller Context-Free Grammars
Theoretical Computer Science, 2010 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Zoltán Ésik, Szabolcs Iván
openaire +2 more sources
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
Weighted Context-Free Grammars Over Bimonoids
Scientific Annals of Computer Science, 2019 We introduce and investigate weighted context-free grammars over an arbitrary bimonoid K. Thus, we do not assume that the operations of K are commutative or idempotent or they distribute over each other.
George Rahonis, Faidra Torpari
doaj +1 more source
Translations on a context free grammar
Information and Control, 1969 Two schemes for the specification of translations on a context-free grammar are proposed. The first scheme, called a generalized syntax directed translation (GSDT), consists of a context free grammar with a set of semantic rules associated with each production of the grammar.
Alfred V. Aho, Jeffrey D. Ullman
openaire +1 more source