The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Complexity results for prefix grammars”

Weightreducing grammars and ultralinear languages

Ulrike Brandt, Ghislain Delepine, Hermann K.-G. Walter (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We exhibit a new class of grammars with the help of weightfunctions. They are characterized by decreasing the weight during the derivation process. A decision algorithm for the emptiness problem is developed. This class contains non-contextfree grammars. The corresponding language class is identical to the class of ultralinear languages.

On the equivalence of linear conjunctive grammars and trellis automata

Alexander Okhotin (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence...

Complexity results for prefix grammars

Markus Lohrey, Holger Petersen (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.

Consensual languages and matching finite-state computations

Stefano Crespi Reghizzi, Pierluigi San Pietro (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

An ever present, common sense idea in language modelling research is that, for a word to be a valid phrase, it should comply with multiple constraints at once. A new language definition model is studied, based on agreement or consensus between similar strings. Considering a regular set of strings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree. Then a regular set over the bipartite alphabet...

Consensual languages and matching finite-state computations

Stefano Crespi Reghizzi, Pierluigi San Pietro (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

An ever present, common sense idea in language modelling research is that, for a word to be a valid phrase, it should comply with multiple constraints at once. A new language definition model is studied, based on agreement or consensus between similar strings. Considering a regular set of strings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree. Then a regular set over the bipartite alphabet...

Bidirectional string assembling systems

Martin Kutrib, Matthias Wendlandt (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We introduce and investigate several variants of a bidirectional string assembling system, which is a computational model that generates strings from copies of assembly units. The underlying mechanism is based on two-sided piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generative capacities and the relative power of the variants are our main interest. In particular, we prove that bidirectional string assembling system...