Displaying similar documents to “Cohesiveness in promise problems”

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.

Complexity results for prefix grammars

Markus Lohrey, Holger Petersen (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et 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.

C++ Tools to construct our user-level language

Frédéric Hecht (2010)

ESAIM: Mathematical Modelling and Numerical Analysis

Similarity:

The aim of this paper is to present how to make a dedicaded computed language polymorphic and multi type, in to solve partial differential equations with the finite element method. The driving idea is to make the language as close as possible to the mathematical notation.

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.

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...

Classes of two-dimensional languages and recognizability conditions

Marcella Anselmo, Maria Madonia (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

The paper deals with some classes of two-dimensional recognizable languages of “high complexity”, in a sense specified in the paper and motivated by some necessary conditions holding for recognizable and unambiguous languages. For such classes we can solve some open questions related to unambiguity, finite ambiguity and complementation. Then we reformulate a necessary condition for recognizability stated by Matz, introducing a new complexity function. We solve an open question proposed...