Wyniki wyszukiwania - Biblioteka Nauki

Ten serwis zostanie wyłączony 2025-02-11.

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

5 Fundamenta Informaticae

Znaleziono wyników: 5

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Active Symbols in Pure Systems

100%

Bensch S. , Bordihn H.

Fundamenta Informaticae

2007

tom Vol. 76, nr 3

239-254

In this paper, we consider the number of (statically measured) active symbols for Lindenmayer systems without interaction and some variants thereof as well as for pure CD grammar systems, where no distinction between terminal and nonterminal symbols is made. This measure of descriptional complexity gives rise to infinite hierarchies in all cases considered here. Moreover, all the devices under consideration are compared with respect to their generative power when the number of active symbols is bounded. Finally, some closure and many non-closure properties of the corresponding language families with a fixed number of active symbols are proved.

Cooperating Distributed Grammar Systems as Models of Distributed Problem Solving, Revisited

100%

Bordihn H. , Holzer M.

Fundamenta Informaticae

2007

tom Vol. 76, nr 3

255-270

Based on a derivation mode f for cooperating distributed (CD) grammar systems, we introduce a new form of cooperation protocol, the so called "cut-f-mode" of derivation. Intuitively, in the cut-f-mode of derivation the sentential form is partitioned (cut) into several subwords, where some of these subwords are distributed to the components, which derive them according to the underlying f-mode of derivation, and finally the new sentential form is obtained by concatenating all the subwords-derived or not-in their original order. According to the original motivation from distributed artificial intelligence, the new functioning mode appears to be more realistic than the original model. We investigate the cut-mode versions of the basic derivation modes and some of their combined versions. It turns out that in most cases, the cut-f-mode is at most as powerful as the corresponding non-cut-mode, that is, the f-mode itself. In some cases the power is even reduced to that of context-free grammars.

Sequential Versus Parallel Grammar Formalisms with Respect to Measures of Descriptional Complexity

100%

Aydin S. , Bordihn H.

Fundamenta Informaticae

2003

tom Vol. 55, nr 3,4

243-254

For tabled Lindenmayer systems and their languages, the degree of synchronization and the degree of nondeterminism are well investigated measures of descriptional complexity. In this paper the sequential counterparts of tabled Lindenmayer systems, namely cooperating distributed grammar systems and their pure variant (working in the so-called t-mode of derivation) are treated with respect to these complexity measures. In the pure case, where no distinction between terminal and nonterminal symbols is made, the sequential mechanisms are compared with the parallel ones, investigating whether one mechanism may have a better descriptional complexity than the other one when the same language is described.

On accepting pure Lindenmayer systems

80%

Bordihn H. , Fernau H. , Holzer M.

Fundamenta Informaticae

1999

tom Vol. 38, Nr 4

365-375

We consider pure Lindenmayer systems, more precisely, 0L and T0L systems as language accepting devices and compare them to their generating counterparts. Accepting Lindenmayer systems can be seen as systems of inverse finite substitutions which are iteratively applied over a free monoid. Hereby, we investigate the deterministic case in detail, comparing several different concepts of determinism in such systems. Whereas in the usual generating case these concepts trivially are equally powerful, the structure of families of accepted languages is much richer. In passing, the case of unary Lindenmayer systems is investigated.

Ambiguity of the Multiple Interpretations on Regular Languages

70%

Alarcón P. P. , Arroyo F. , Bordihn H. , Mitrana V. , Müller M.

Fundamenta Informaticae

2015

tom Vol. 138, nr 1/2

85--95

A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages.