Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

2 2012

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages

Rampersad N., Shallit J., Xu Z.

Fundamenta Informaticae

2012

Vol. 116, nr 1-4

223-236

In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Σ, is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal to Σ*? In the case of testing universality for factors of languages, there is a connection to two classic problems: the synchronizing words problem of Černy, and Restivo's conjecture on the minimal uncompletable word.

Syntactic Complexity of Ultimately Periodic Sets of Integers and Application to a Decision Procedure

Lacroix A., Rampersad N., Rigo M., Vandomme Ë.

Fundamenta Informaticae

2012

Vol. 116, nr 1-4

175-187

We compute the cardinality of the syntactic monoid of the language 0*rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to a well studied problem: decide whether or not a b-recognizable set of integers is ultimately periodic.