PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 17

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  contextual grammars
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Generative Capacity of Contextual Grammars with Subregular Selection Languages
Truthe Bianca
Fundamenta Informaticae
|
2021
|
Vol. 180, nr 1-2
123--150
EN
A contextual grammar is a language generating mechanism inspired by generating sentences in natural languages. An existing string can be extended to a new string of the language by adjoining a context before and behind the string or by inserting it into the string around some subword. The first mode is called external derivation whereas the second mode is called internal derivation. If conditions are given, around which words which contexts can be adjoined, we speak about contextual grammars with selection. We give an overview about the generative capacity of contextual grammars (working externally or internally) where the selection languages belong to subregular language classes. All languages generated by contextual grammars where all selection languages are elements of a certain subregular language family form again a language family. We compare such families which are based on finite, monoidal, nilpotent, combinational, definite, suffix-closed, ordered, commutative, circular, non-counting, power-separating, or union-free languages, or based on languages defined by restrictions regarding the descriptional complexity.
2
Content available remote Non-Isometric Contextual Array Grammars and the Role of Regular Control and Local Selectors
Fernau H., Siromoney R., Freund R., Subramanian K. G.
Fundamenta Informaticae
|
2017
|
Vol. 155, nr 1/2
209--232
EN
We consider the external variant of non-isometric d-dimensional contextual array grammars with regular control together with local selectors allowing for controlling how d-dimensional arrays are evolving by adjoining rectangular (d-1)-dimensional arrays. In the 1-dimensional case, the computational power of these non-isometric contextual array grammars with regular control and local selectors equals the computational power of isometric contextual array grammars with regular control. The string images of the languages of 1-dimensional arrays generated by these contextual array grammars exactly yield the linear languages. In the more-dimensional case, non-isometric d-dimensional contextual array grammars with regular control and local selectors can simulate the computations of (d - 1)-dimensional array grammars or Turing machines. Hence, for example, the emptiness problem for non-isometric d-dimensional contextual array grammars with regular control and local selectors for d > 1 is undecidable. We also compare the computational power of all variants of non-isometric d-dimensional contextual array grammars that we introduce to each other.
3
Content available remote Syllabic Languages and Go-through Automata
Dinu L.P., Gramatovici R., Manea F.
Fundamenta Informaticae
|
2014
|
Vol. 131, nr 3-4
409--424
EN
In this paper we define a new class of contextual grammars and study how the languages generated by such grammars can be accepted by go-through automata. The newly introduced class of grammars is a generalization of the formalism previously used to describe the linguistic process of syllabification. Go-through automata which are used here to recognize, and also parse, the languages generated by this new class of grammars are generalizations of push-down automata in the area of context-sensitivity; they have been proved to be an efficient tool for the recognition of languages generated by contextual grammars. The main results of the paper show how the newly introduced generative model is related with other classes of Marcus contextual languages, and how syllabic languages are recognized and parsed using go-through automata.
4
Content available remote On Insertion Grammars with Maximum Parallel Derivation
Dinu L.P.
Fundamenta Informaticae
|
2009
|
Vol. 93, nr 4
357-369
EN
In this paper we investigate insertion grammars and explore their capacity to generate words parallelly by introducing parallel derivation (where more than one rule can be applied to the string in parallel) and maximum parallel derivation (where as many rules as possible are applied to the string in parallel). We compare the generative power of these grammars with context sensitive and context free grammars and with different variants of contextual grammars. We apply these grammars to syllabification in Romanian and provide arguments that they can also be used in a cognitive perspective.
5
Content available remote Array Grammars with Contextual Operations
Subramanian K.G., Van Do Long, Chandra P.H., Quyen N.D.
Fundamenta Informaticae
|
2008
|
Vol. 83, nr 4
411-428
EN
In this paper, we consider a class of two-dimensional array grammars, called parallel contextual array grammars, that extend the contextual operations on strings to arrays in a natural way and generate languages of pictures of rectangular arrays. Several classes of these array grammars and the resulting families of picture languages are considered. Necessary conditions for picture languages to be contained in these classes are obtained and the relations between these families are also established.
6
Content available remote Representations of Recursively Enumerable Array Languages by Contextual Array Grammars
Fernau H., Freund R., Holzer M.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
159-170
EN
The main result proved in this paper shows that the natural embedding of any recursively enumerable one-dimensional array language in the two-dimensional space can be characterized by the projection of a two-dimensional array language generated by a contextual array grammar working in the t-mode and with norm one. Moreover, we show that any recursively enumerable one-dimensional array language can even be characterized by the projection of a two-dimensional array language generated by a contextual array grammar working in the t-mode where in the selectors of the contextual array productions only the ability to distinguish between blank and non-blank positions is necessary; in that case, the norm of the two-dimensional contextual array grammar working in the t-mode cannot be bounded.
7
Content available remote Parsing Local Internal Contextual Languages with Context-Free Choice
Gramatovici R., Manea F.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
171-183
EN
We extend the result from [8] by giving also a concrete polynomial parsing algorithm for a class of languages generated by a variant of contextual grammars, namely local internal contextual grammars with context-free choice.
8
Content available remote On the Relationship Between Multiple Brackets and Selector Languages in Bracketed Contextual Grammars
Kappes M.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
229-239
EN
Bracketed contextual grammars are a variant of Marcus' contextual grammars with an induced Dyck-structure to control the derivation process and to provide derivation trees. Many variants of bracketed contextual grammars have been proposed in literature. In this paper, we study the relationship between various mechanisms in such grammars, in particular the number of brackets, the used selector languages, and the ability to introduce more than a single pair of brackets in a derivation step, with respect to the generative capacity of the resulting models.
9
Content available remote On Probabilistic Contextual Grammars
Kudlek M.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
255-260
EN
A generalization of contextual grammars by adding probabilities is introduced, enriching the generative power of such grammars. An example exhibits a non-contextual, even not context-free language.
10
Content available remote On Characterizing Recursively Enumerable Languages by Insertion Grammars
Mutyam M., Krithivasan K., Reddy A. S.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
317--324
EN
Insertion grammars have been introduced in [1] and their computational power has been studied in several places. In [7] it is proved that insertion grammars with weight at least 7 can characterize recursively enumerable languages (modulo a weak coding and an inverse morphism), and the question was formulated whether or not this result can be improved. In this paper, we come up with a positive answer to this question, by decreasing the weight of the insertion grammar used to 5. We also give a characterization of recursively enumerable languages in terms of right quotients of insertion languages.
11
Content available remote Further Results on Contextual and Rewriting P Systems
Krishna S. N., Rama R., Ramesh H.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
241-253
EN
In this paper, we continue the study of contextual and rewriting P systems. In contextual P systems, we improve a universality result avoiding the extended feature and by using rules of small weight. In rewriting P systems, we have two (rather surprising) universality results, both of them using three membranes, for non-extended systems with replicated rewriting and with leftmost rewriting, respectively.
12
Content available remote Deterministic Two-Way Restarting Automata and Marcus Contextual Grammars
Jurdziński T., Otto F., Mráz F., Plátek M.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
217-228
EN
It is known that for (right-) monotone deterministic one-way restarting automata, the use of auxiliary symbols does not increase the expressive power. Here we show that the same is true for deterministic two-way restarting automata that are right-left-monotone. Moreover, we present a transformation of this kind of restarting automata into contextual grammars with regular selection.
13
Content available remote Contextual Grammars with Uniform Sets of Trajectories
Okhotin A., Salomaa K.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
341-351
EN
A uniform contextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the non-uniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.
14
Content available remote Contextual Grammars with Subregular Choice
Dassow J.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
109-118
EN
We discuss external contextual grammars with choice where the choice language belongs to a family of subregular languages. We determine the hierarchy of language families of contextual languages which is obtained by the use of nilpotent, combinational, definite, regular suffix closed, and regular commutative languages as choice languages.
15
Content available remote Construction of Contextual Grammars
Novotny M.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
325-340
EN
The concept of a contextual grammar is slightly generalized here; the generalized grammars called contextual hypergrammars admit to introduce the so called reducing operators. Using some results concerning these operators a construction is described assigning a contextual grammar Gn(V,L) to any language (V,L) and to any nonnegative integer n. This construction has the following property: The language (V,L) is generated by a contextual grammar if and only if there exists a nonnegative integer n0 such that Gn(V,L) = Gn0(V,L) for any > n0.
16
Content available remote Contextual P Systems
Krithivasan K., Madhu M.
Fundamenta Informaticae
|
2002
|
Vol. 49, nr 1-3
179-189
EN
Generally, in P systems with string-objects one uses the Chomsky way of rewriting for processing the objects. In this paper we consider the contextual way of handling string-objects in P systems. We introduce some variants of contextual grammars and prove that contextual P systems with rules corresponding to these variants are more powerful than ordinary contextual grammars and their variants. We also show that one-sided contextual P systems with right-sided erased contexts and insertion contextual P systems with right-sided erased contexts are computationally complete.
17
Content available remote Multi-bracketed contextual rewriting grammars
Kappes M.
Fundamenta Informaticae
|
1999
|
Vol. 38, Nr 3
257-280
EN
We study the generative capacity of multi-bracketed contextual rewriting grammars. This model is a generalization of multi-bracketed contextual grammars, which were studied in [Kap98a]. They possess an induced Dyck-structure to control the derivation process and to provide derivation trees. The generative capacity of this class is investigated and compared to Chomsky grammars and to tree adjoining grammars with local constraints. It will be shown that this class of grammars covers the basic natural language constructions such as duplication, multiple agreement and crossed-serial dependencies. Furthermore, two natural variants of the derivation relation, namely top-down and bottom-up derivation modes are examined.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.