Wyniki wyszukiwania - BazTech

Ograniczanie wyników

4 Fundamenta Informaticae

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: w-languages

Sortuj według:

Ogranicz wyniki do:

Regular w-Languages Defined by Finite Extended Spiking Neural P Systems

Freund R., Oswald M.

Fundamenta Informaticae

2008

Vol. 83, nr 1-2

65-73

We investigate finite extended spiking neural P systems as acceptors for infinite sequences of symbols 1 and 0, i.e., of w-words over { 0,1} . We show that regular w-languages over { 0,1} can be characterized by deterministic/non-deterministic finite extended spiking neural P systems accepting w-words in specific modes with respect to the infinite sequence of states the finite extended spiking neural P systems go through during the accepting computations.

Complexity of Topological Properties of Regular w-Languages

Selivanov V.L., Wagner K.W.

Fundamenta Informaticae

2008

Vol. 83, nr 1-2

197-217

We determine the complexity of topological properties (i.e., properties closed under the Wadge equivalence) of regular w-languages by showing that they are typically NL-complete (PSPACE-complete) for the deterministic Muller, Mostowski and Büchi automata (respectively, for the nondeterministic Rabin, Muller, Mostowski and Büchi automata). For the deterministic Rabin and Streett automata and for the nondeterministic Streett automata upper and lower complexity bounds for the topological properties are established.

Blind Counter Automata on w-Words

Fernau H., Stiebe R.

Fundamenta Informaticae

2008

Vol. 83, nr 1-2

51-64

This paper generalizes the concept of blind multicounter languages to infinite words. We introduce two different acceptance modes of blind multicounter machines on w-words, called synchrononous and asynchronous acceptance. These acceptance modes are compared with each other and with families of w-languages of the form L=[formula], where Ui, Vi are finitary blind multicounter languages.

An ω-Power of a Finitary Language Which is a Borel Set of Infinite Rank

Finkel O.

Fundamenta Informaticae

2004

Vol. 62, nr 3,4

333--342

ω-powers of finitary languages are ω-languages s in the form Vω, where V is a finitary language over a finite alphabet Σ. Since the set Σ,sup>ω of infinite words over Σ can be equipped with the usual Cantor topology, the question of the topological complexity of ω-powers naturally arises and has been raised by Niwinski [13], by Simonnet [15], and by Staiger [18]. It has been proved in [4] that for each integer n ≥ 1, there exist some ω-powers of context free languages which are Πn0-complete Borel sets, and in [5] that there exists a context free language L such that Lω is analytic but not Borel. But the question was still open whether there exists a finitary language V such that Vω is a Borel set of infinite rank. We answer this question in this paper, giving an example of a finitary language whose ω-power is Borel of infinite rank.