English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We solve open problems concerning the Kleene starof a finite setof words over an alphabet. TheFrobenius monoid problem is the question for a given finite set of words, whether the languageis cofinite. We show that it is PSPACE-complete. We also exhibit an infinite family of setssuch that the length of the longest words not in(whenis cofinite) is exponential in the length of the longest words inand subexponential in the sum of the lengths of words in. Thefactor universality problem is the question for a given finite set of words, whether every word overis a factor (substring) of some word from. We show that it is also PSPACE-complete. Besides that, we exhibit an infinite family of setssuch that the length of the shortest words not being a factor of any word inis exponential in the length of the longest words inand subexponential in the sum of the lengths of words in. This essentially settles in the negative the longstanding Restivo’s conjecture (1981) and its weak variations. All our solutions are based on one shared construction, and as an auxiliary general tool, we introduce the concept ofset rewriting systems . Finally, we complement the results with upper bounds.

The Frobenius and Factor Universality Problems of the Kleene Star of a Finite Set of Words