Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: pure grammar

Sortuj według:

Ogranicz wyniki do:

Decidability Questions for Insertion Systems and Related Models

Malcher Andreas

Fundamenta Informaticae

2021

Vol. 180, nr 1-2

53--76

Insertion systems or insertion grammars are a generative formalism in which words can only be generated by starting with some axioms and by iteratively inserting strings subject to certain contexts of a fixed maximal length. It is known that languages generated by such systems are always context sensitive and that the corresponding language classes are incomparable with the regular languages. On the other hand, it is possible to generate non-semilinear languages with systems having contexts of length two. Here, we study decidability questions for insertion systems. On the one hand, it can be seen that emptiness and universality are decidable. Moreover, the fixed membership problem is solvable in deterministic polynomial time. On the other hand, the usually studied decidability questions such as, for example, finiteness, inclusion, equivalence, regularity, inclusion in a regular language, and inclusion of a regular language turn out to be undecidable. Interestingly, the latter undecidability results can be carried over to other models which are basically able to handle the mechanism of inserting strings depending on contexts. In particular, new undecidability results are obtained for pure grammars, restarting automata, clearing restarting automata, and forgetting automata.

Construction of Pure Grammars

Novotny M.

Fundamenta Informaticae

2002

Vol. 52, nr 4

345-360

A construction is described assigning a pure grammar G_mrn to any language and to any integers 0 < m < r < n. This construction has the following property: If the sequence (Gmrn)n > r has a limit Gmr for any r > m and if the sequence (Gmr)r > m has a limit, then the given language is generated by a pure grammar. By a limit of a sequence (ak)k >k_0 we understand a member a_k1 of the sequence such that k_1 > k_0 and a_k = a_k1 for any k > k_1.

Reduction of pregrammars

Novotny M.

Fundamenta Informaticae

1998

Vol. 33, nr 3

295-307

In pure generalized grammars were studied, in particular, the problem of reducing a pure generalized grammar to a pure grammar. These results are transferred to the so called pregrammars in the present paper. The obtained results may be applied not only to pure generalized grammars but also to other structures.