Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Szilard languages

Sortuj według:

Ogranicz wyniki do:

On Szilard Languages of Labelled Insertion Grammars

Prithwinee Paul

Fundamenta Informaticae

2020

Vol. 172, nr 1

53--72

In this work we initiate the study of Szilard languages of labelled insertion grammars. It is well-known that there exist context-free languages which cannot be generated by any insertion grammar. We show that there exist some regular languages which cannot be Szilard language of any labelled insertion grammar. But any regular language can be given as a homomorphic image of Szilard language obtained by a labelled insertion grammar of weight 1. Also, any context-free language can be obtained as a homomorphic image of Szilard language of a labelled insertion grammar of weight 2. We show that even though insertion grammars of weight 1 can generate only context-free languages, there exists some context-sensitive language which can be obtained as Szilard language of a labelled insertion grammar of weight 1. At the end we show that any recursively enumerable language can be characterized by the homomorphic image of Szilard language obtained by a labelled insertion grammar of weight 5.

The Complexity of Szilard Languages of Matrix Grammars Revisited

Cojocaru L., Mäkinen E.

Fundamenta Informaticae

2013

Vol. 123, nr 4

381--399

The regulated rewriting mechanism is one of the most efficient methods to augment the Chomsky hierarchy with a large variety of language classes. In this paper we investigate the derivation mechanism in regulated rewriting grammars such as matrix grammars, by studying their Szilard languages. We focus on the complexity of Szilard languages associated with unrestricted and leftmost-like derivations in matrix grammars, with or without appearance checking. The reason is twofold. First, to relate these classes of languages to parallel complexity classes such as NC1 and AC1, and, second, to improve some previous results. We prove that unrestricted Szilard languages and certain leftmost Szilard languages of context-free matrix grammars, without appearance checking, can be accepted by indexing alternating Turing machines in logarithmic time and space. Consequently, these classes are included in UE-uniform NC1. Unrestricted Szilard languages of matrix grammars with appearance checking can be accepted by deterministic Turing machines in O(n log n) time and O(log n) space. Leftmost-like Szilard languages of context-free matrix grammars, with appearance checking, can be recognized by nondeterministic Turing machines by using the same time and space resources. Hence, all these classes are included in AC1.