Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: sofic shift

Sortuj według:

Ogranicz wyniki do:

Algorithmic Approach to Devaney Chaos in Shift Spaces

Oprocha P.

Fundamenta Informaticae

2008

Vol. 87, nr 3-4

435-446

Among the class of sofic shifts Devaney chaos is equivalent to topological transitivity. The aim of this paper is to study possibilities of detection of this phenomena when a right-resolving graph presentation of a sofic shift is given. We show that Devaney chaos detection is co-NP-hard problem and point out some possible improvements of algorithms known from the literature.

Computing forbidden words of regular languages

Béal M-P., Crochemore M., Mignosi F., Restivo A., Sciortino M.

Fundamenta Informaticae

2003

Vol. 56, nr 1,2

121-135

We give a quadratic-time algorithm to compute the set of minimal forbidden words of a factorial regular language. We give a linear-time algorithm to compute the minimal forbidden words of a finite set of words. This extends a previous result given for the case of a single word only. We also give quadratic-time algorithms to check whether a regular language is factorial or anti-factorial.