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 star $L^*$ of a finite set $L$of words over an alphabet $\Sigma$. The \emph{Frobenius monoid} problem is thequestion for a given finite set of words $L$, whether the language $L^*$ iscofinite. We show that it is PSPACE-complete. We also exhibit an infinitefamily of sets $L$ such that the length of the longest words not in $L^*$ (when$L^*$ is cofinite) is exponential in the length of the longest words in $L$ andsubexponential in the sum of the lengths of words in $L$. The \emph{factoruniversality} problem is the question for a given finite set of words $L$,whether every word over $\Sigma$ is a factor (substring) of some word from$L^*$. We show that it is also PSPACE-complete. Besides that, we exhibit aninfinite family of sets $L$ such that the length of the shortest words notbeing a factor of any word in $L^*$ is exponential in the length of the longestwords in $L$ and subexponential in the sum of the lengths of words in $L$. Thisessentially settles in the negative the longstanding Restivo's conjecture(1981) and its weak variations. All our solutions base on one sharedconstruction, and as an auxiliary general tool, we introduce the concept of\emph{set rewriting systems}. Finally, we complement the results with upperbounds.

The Frobenius and factor universality problems of the Kleene star of a finite set of words