Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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.

Characterization Results for Time-Varying Codes

Tiplea F.L., Mäkinen E., Trinca D., Enea C.

Fundamenta Informaticae

2002

Vol. 53, nr 2

185-198

Time-varying codes associate variable length code words to letters being encoded depending on their positions in the input string. These codes have been introduced in [8] as a proper extension of L codes. This paper is devoted to a further study of time-varying codes. First, we show that adaptive Huffman encodings are special cases of encodings by time-varying codes. Then, we focus on three kinds of characterization results: characterization results based on decompositions over families of sets of words, a Schützenberger like criterion, and a Sardinas-Patterson like characterization theorem. All of them extend the corresponding characterization results known for classical variable length codes.

A note on SE-Systems and regular canonical systems

Tiplea F.L., Mäkinen E.

Fundamenta Informaticae

2001

Vol. 46, nr 3

253-256

A synchronized extension system is a 4-tuple G = (V,L1,L2,S), where V is an alphabet and L1, L2 and S are languages over V. Such systems generate languages extending L1 by L2 to the left or to the right, and synchronizing on words in S. In this note we consider the relationship between synchronized extension systems and regular canonical systems. We are able to give a simplified and generalized proof for the classical result concerning the regularity of the languages defined by regular canonical systems.