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: multisequential grammars

Sortuj według:

Ogranicz wyniki do:

On Descriptional Complexity of Partially Parallel Grammars

Masopust T., Meduna A.

Fundamenta Informaticae

2008

Vol. 87, nr 3-4

407-415

This paper presents some new results concerning the descriptional complexity of partially parallel grammars. Specifically, it proves that every recursively enumerable language is generated (i) by a four-nonterminal scattered context grammar with no more than four non-context-free productions, (ii) by a two-nonterminal multisequential grammar with no more than two selectors, or (iii) by a three-nonterminalmulticontinuous grammar with no more than two selectors.

Multisequential Grammars with Homogeneous Selectors

Meduna A., Vurm P.

Fundamenta Informaticae

2001

Vol. 48, nr 1

55-60

This paper deals with selective substitution grammars. It concentrates on multisequential grammars with homogeneous selectors that have all their activated parts identical. The present paper reduces the number and size of selectors in these grammars. Indeed, it demonstrates that for every phrase-structure grammar, there exists an equivalent multisequential grammar having two homogeneous selectors, either of which has only two activated parts.