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/

Zendy Plus

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

Zendy Tools

Zendy Open

The aim of this paper is to present a PSPACE algorithm which yields a finitegraph of exponential size and which describes the set of all solutions ofequations in free groups as well as the set of all solutions of equations infree monoids with involution in the presence of rational constraints. Thisbecame possible due to the recently invented emph{recompression} technique ofthe second author.  He successfully applied the recompression technique for pure word equationswithout involution or rational constraints. In particular, his method could notbe used as a black box for free groups (even without rational constraints).Actually, the presence of an involution (inverse elements) and rationalconstraints complicates the situation and some additional analysis isnecessary. Still, the recompression technique is general enough to accommodateboth extensions. In the end, it simplifies proofs that solving word equationsis in PSPACE (Plandowski 1999) and the corresponding result for equations infree groups with rational constraints (Diekert, Hagenah and Gutierrez 2001). Asa byproduct we obtain a direct proof that it is decidable in PSPACE whether ornot the solution set is finite.

Finding All Solutions of Equations in Free Groups and Monoids with Involution