Nowotka, Dirk; Saarela, Aleksi An optimal bound on the solution sets of one-variable word equations and its consequences. (English) Zbl 1492.68115 SIAM J. Comput. 51, No. 1, 1-18 (2022). Reviewer: Štěpán Holub (Praha) MSC: 68R15 PDFBibTeX XMLCite \textit{D. Nowotka} and \textit{A. Saarela}, SIAM J. Comput. 51, No. 1, 1--18 (2022; Zbl 1492.68115) Full Text: DOI arXiv
Whiteland, Markus A. Equations over the \(k\)-binomial monoids. (English) Zbl 1497.68407 Lecroq, Thierry (ed.) et al., Combinatorics on words. 13th international conference, WORDS 2021, Rouen, France, September 13–17, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12847, 185-197 (2021). Reviewer: Anna Frid (Marseille) MSC: 68R15 20M35 PDFBibTeX XMLCite \textit{M. A. Whiteland}, Lect. Notes Comput. Sci. 12847, 185--197 (2021; Zbl 1497.68407) Full Text: DOI
Harju, Tero; Karhumäki, Juhani Finite transducers and rational transductions. (English) Zbl 1517.68195 Pin, Jean-Éric (ed.), Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS). 79-111 (2021). Reviewer: Andreas Maletti (Leipzig) MSC: 68Q45 68Q70 PDFBibTeX XMLCite \textit{T. Harju} and \textit{J. Karhumäki}, in: Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS). 79--111 (2021; Zbl 1517.68195) Full Text: DOI
Gilbert, N. D.; McDougall, E. A. Groupoids and the algebra of rewriting in group presentations. (English) Zbl 1496.20055 Beitr. Algebra Geom. 62, No. 3, 623-639 (2021). MSC: 20F05 20J05 20L05 20F10 68Q42 PDFBibTeX XMLCite \textit{N. D. Gilbert} and \textit{E. A. McDougall}, Beitr. Algebra Geom. 62, No. 3, 623--639 (2021; Zbl 1496.20055) Full Text: DOI arXiv
Bartholdi, Laurent; Figelius, Michael; Lohrey, Markus; Weiß, Armin Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems. (English) Zbl 07561757 Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 29, 29 p. (2020). MSC: 68Q25 PDFBibTeX XMLCite \textit{L. Bartholdi} et al., LIPIcs -- Leibniz Int. Proc. Inform. 169, Article 29, 29 p. (2020; Zbl 07561757) Full Text: DOI arXiv
Karhumäki, Juhani; Whiteland, Markus A. A compactness property of the \(k\)-abelian monoids. (English) Zbl 1448.68368 Theor. Comput. Sci. 834, 3-13 (2020). Reviewer: Michel Rigo (Liège) MSC: 68R15 20M99 PDFBibTeX XMLCite \textit{J. Karhumäki} and \textit{M. A. Whiteland}, Theor. Comput. Sci. 834, 3--13 (2020; Zbl 1448.68368) Full Text: DOI
Corwin, Nathan; Golan, Gili; Hermiller, Susan; Johnson, Ashley; Šunić, Zoran Autostackability of Thompson’s group \(F\). (English) Zbl 1485.20080 J. Algebra 545, 111-134 (2020). MSC: 20F10 20F65 68Q42 PDFBibTeX XMLCite \textit{N. Corwin} et al., J. Algebra 545, 111--134 (2020; Zbl 1485.20080) Full Text: DOI arXiv
Muscholl, Anca; Puppis, Gabriele Equivalence of finite-valued streaming string transducers is decidable. (English) Zbl 07561615 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 122, 15 p. (2019). MSC: 68Nxx 68Qxx PDFBibTeX XMLCite \textit{A. Muscholl} and \textit{G. Puppis}, LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 122, 15 p. (2019; Zbl 07561615) Full Text: DOI arXiv
Muscholl, Anca; Puppis, Gabriele The many facets of string transducers (Invited Talk). (English) Zbl 07559111 Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 2, 21 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Muscholl} and \textit{G. Puppis}, LIPIcs -- Leibniz Int. Proc. Inform. 126, Article 2, 21 p. (2019; Zbl 07559111) Full Text: DOI
Nowotka, Dirk; Saarela, Aleksi An optimal bound on the solution sets of one-variable word equations and its consequences. (English) Zbl 1492.68114 Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 136, 13 p. (2018). MSC: 68R15 PDFBibTeX XMLCite \textit{D. Nowotka} and \textit{A. Saarela}, LIPIcs -- Leibniz Int. Proc. Inform. 107, Article 136, 13 p. (2018; Zbl 1492.68114) Full Text: DOI
Nowotka, Dirk; Saarela, Aleksi One-variable word equations and three-variable constant-free word equations. (English) Zbl 1473.68131 Int. J. Found. Comput. Sci. 29, No. 5, 935-950 (2018). Reviewer: Jean-Luc Baril (Dijon) MSC: 68R15 PDFBibTeX XMLCite \textit{D. Nowotka} and \textit{A. Saarela}, Int. J. Found. Comput. Sci. 29, No. 5, 935--950 (2018; Zbl 1473.68131) Full Text: DOI
Cain, Alan J.; Gray, Robert D.; Malheiro, António On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids. (English) Zbl 1371.68135 Inf. Comput. 255, Part 1, 68-93 (2017). MSC: 68Q42 20M35 PDFBibTeX XMLCite \textit{A. J. Cain} et al., Inf. Comput. 255, Part 1, 68--93 (2017; Zbl 1371.68135) Full Text: DOI arXiv Link
Bleak, Collin; Matucci, Francesco; Neunhöffer, Max Embeddings into Thompson’s group \(V\) and \(\mathrm{co}\mathcal{C}{F}\) groups. (English) Zbl 1406.20042 J. Lond. Math. Soc., II. Ser. 94, No. 2, 583-597 (2016). MSC: 20F10 20E08 68Q45 03D40 PDFBibTeX XMLCite \textit{C. Bleak} et al., J. Lond. Math. Soc., II. Ser. 94, No. 2, 583--597 (2016; Zbl 1406.20042) Full Text: DOI arXiv Backlinks: MO
Nowotka, Dirk; Saarela, Aleksi One-unknown word equations and three-unknown constant-free word equations. (English) Zbl 1436.68284 Brlek, Srečko (ed.) et al., Developments in language theory. 20th international conference, DLT 2016, Montréal, Canada, July 25–28, 2016. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9840, 332-343 (2016). MSC: 68R15 PDFBibTeX XMLCite \textit{D. Nowotka} and \textit{A. Saarela}, Lect. Notes Comput. Sci. 9840, 332--343 (2016; Zbl 1436.68284) Full Text: DOI
Antolín, Yago; Sale, Andrew W. Permute and conjugate: the conjugacy problem in relatively hyperbolic groups. (English) Zbl 1396.20030 Bull. Lond. Math. Soc. 48, No. 4, 657-675 (2016). MSC: 20F10 20F65 20F67 68Q25 PDFBibTeX XMLCite \textit{Y. Antolín} and \textit{A. W. Sale}, Bull. Lond. Math. Soc. 48, No. 4, 657--675 (2016; Zbl 1396.20030) Full Text: DOI arXiv
Leupold, Peter General idempotency languages over small alphabets. (English) Zbl 1344.68125 Int. J. Found. Comput. Sci. 27, No. 3, 343-357 (2016). MSC: 68Q45 68Q42 PDFBibTeX XMLCite \textit{P. Leupold}, Int. J. Found. Comput. Sci. 27, No. 3, 343--357 (2016; Zbl 1344.68125) Full Text: DOI
Elder, Murray; Taback, Jennifer Thompson’s group \(F\) is 1-counter graph automatic. (English) Zbl 1344.20043 Groups Complex. Cryptol. 8, No. 1, 21-33 (2016). MSC: 20F10 20F65 68Q45 20F05 PDFBibTeX XMLCite \textit{M. Elder} and \textit{J. Taback}, Groups Complex. Cryptol. 8, No. 1, 21--33 (2016; Zbl 1344.20043) Full Text: DOI arXiv
Saarela, Aleksi Systems of word equations, polynomials and linear algebra: a new approach. (English) Zbl 1403.68177 Eur. J. Comb. 47, 1-14 (2015). MSC: 68R15 68Q25 PDFBibTeX XMLCite \textit{A. Saarela}, Eur. J. Comb. 47, 1--14 (2015; Zbl 1403.68177) Full Text: DOI arXiv
Holub, Štěpán; Žemlička, Jan Algebraic properties of word equations. (English) Zbl 1318.68133 J. Algebra 434, 283-301 (2015). Reviewer: Panayiotis Vlamos (Athena) MSC: 68R15 PDFBibTeX XMLCite \textit{Š. Holub} and \textit{J. Žemlička}, J. Algebra 434, 283--301 (2015; Zbl 1318.68133) Full Text: DOI arXiv
Gray, R. D.; Malheiro, A. Homotopy bases and finite derivation type for subgroups of monoids. (English) Zbl 1334.20055 J. Algebra 410, 53-84 (2014). MSC: 20M50 20M05 68Q42 20M35 PDFBibTeX XMLCite \textit{R. D. Gray} and \textit{A. Malheiro}, J. Algebra 410, 53--84 (2014; Zbl 1334.20055) Full Text: DOI arXiv
Olshanskii, A. Yu. Space functions and space complexity of the word problem in semigroups. (English) Zbl 1322.20054 Comput. Complexity 22, No. 4, 771-830 (2013). Reviewer: Jörg Lehnert (Leipzig) MSC: 20M05 03D40 03D10 03D15 20F10 20F06 20F69 68Q15 68Q25 PDFBibTeX XMLCite \textit{A. Yu. Olshanskii}, Comput. Complexity 22, No. 4, 771--830 (2013; Zbl 1322.20054) Full Text: DOI
Olshanskii, A. Yu. Space functions of groups. (English) Zbl 1287.20045 Trans. Am. Math. Soc. 364, No. 9, 4937-4985 (2012). Reviewer: Jörg Lehnert (Leipzig) MSC: 20F05 20F06 20F10 20F65 20F69 03D10 03D15 03D40 68Q15 68Q17 PDFBibTeX XMLCite \textit{A. Yu. Olshanskii}, Trans. Am. Math. Soc. 364, No. 9, 4937--4985 (2012; Zbl 1287.20045) Full Text: DOI arXiv
Huova, Mari; Karhumäki, Juhani Equations in the partial semigroup of words with overlapping products. (English) Zbl 1367.68214 Bordihn, Henning (ed.) et al., Languages alive. Essays dedicated to Jürgen Dassow on the occasion of his 65th birthday. Berlin: Springer (ISBN 978-3-642-31643-2/pbk). Lecture Notes in Computer Science 7300, 99-110 (2012). MSC: 68R15 20M35 PDFBibTeX XMLCite \textit{M. Huova} and \textit{J. Karhumäki}, Lect. Notes Comput. Sci. 7300, 99--110 (2012; Zbl 1367.68214) Full Text: DOI
Karhumäki, Juhani; Saarela, Aleksi On maximal chains of systems of word equations. (English) Zbl 1297.68193 Proc. Steklov Inst. Math. 274, 116-123 (2011) and Tr. Mat. Inst. Steklova 274, 130-136 (2011). MSC: 68R15 PDFBibTeX XMLCite \textit{J. Karhumäki} and \textit{A. Saarela}, Proc. Steklov Inst. Math. 274, 116--123 (2011; Zbl 1297.68193) Full Text: DOI arXiv
Sapir, Mark Asymptotic invariants, complexity of groups and related problems. (English) Zbl 1293.20041 Bull. Math. Sci. 1, No. 2, 277-364 (2011). Reviewer: Stratos Prassidis (Karlovassi) MSC: 20F65 20F10 20-02 20F67 20F69 68Q25 20F38 20F50 PDFBibTeX XMLCite \textit{M. Sapir}, Bull. Math. Sci. 1, No. 2, 277--364 (2011; Zbl 1293.20041) Full Text: DOI arXiv
Plyushchenko, A. N. On the word problem for the free Burnside semigroups satisfying \(x^2=x^3\). (English. Russian original) Zbl 1254.20046 Russ. Math. 55, No. 11, 76-79 (2011); translation from Izv. Vyssh. Uchebn. Zaved., Mat. 2011, No. 11, 89-93 (2011). MSC: 20M05 68R15 20M35 PDFBibTeX XMLCite \textit{A. N. Plyushchenko}, Russ. Math. 55, No. 11, 76--79 (2011; Zbl 1254.20046); translation from Izv. Vyssh. Uchebn. Zaved., Mat. 2011, No. 11, 89--93 (2011) Full Text: DOI
Plyushchenko, Andrey N.; Shur, Arseny M. Almost overlap-free words and the word problem for the free Burnside semigroup satisfying \(x^2=x^3\). (English) Zbl 1242.20064 Int. J. Algebra Comput. 21, No. 6, 973-1006 (2011). Reviewer: Ahmet Sinan Çevik (Konya) MSC: 20M05 68R15 20M18 PDFBibTeX XMLCite \textit{A. N. Plyushchenko} and \textit{A. M. Shur}, Int. J. Algebra Comput. 21, No. 6, 973--1006 (2011; Zbl 1242.20064) Full Text: DOI arXiv
Gray, R.; Malheiro, A.; Pride, S. J. On properties not inherited by monoids from their Schützenberger groups. (English) Zbl 1279.20069 Inf. Comput. 209, No. 7, 1120-1134 (2011). Reviewer: Aleksandr V. Tishchenko (Moskva) MSC: 20M05 68Q42 20M35 20F05 20F10 PDFBibTeX XMLCite \textit{R. Gray} et al., Inf. Comput. 209, No. 7, 1120--1134 (2011; Zbl 1279.20069) Full Text: DOI arXiv
Elder, Murray; Fusy, Éric; Rechnitzer, Andrew Counting elements and geodesics in Thompson’s group \(F\). (English) Zbl 1201.20038 J. Algebra 324, No. 1, 102-121 (2010). MSC: 20F65 20F05 68W30 05A16 PDFBibTeX XMLCite \textit{M. Elder} et al., J. Algebra 324, No. 1, 102--121 (2010; Zbl 1201.20038) Full Text: DOI arXiv
Saarela, Aleksi On the complexity of Hmelevskii’s theorem and satisfiability of three unknown equations. (English) Zbl 1247.68214 Diekert, Volker (ed.) et al., Developments in language theory. 13th international conference, DLT 2009, Stuttgart, Germany, June 30–July 3, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02736-9/pbk). Lecture Notes in Computer Science 5583, 443-453 (2009). MSC: 68R15 68Q25 PDFBibTeX XMLCite \textit{A. Saarela}, Lect. Notes Comput. Sci. 5583, 443--453 (2009; Zbl 1247.68214) Full Text: DOI
Birget, Jean-Camille One-way permutations, computational asymmetry and distortion. (English) Zbl 1205.20044 J. Algebra 320, No. 11, 4030-4062 (2008). MSC: 20F10 20F05 68Q25 20M05 68P25 68Q15 94C10 PDFBibTeX XMLCite \textit{J.-C. Birget}, J. Algebra 320, No. 11, 4030--4062 (2008; Zbl 1205.20044) Full Text: DOI arXiv
Karhumäki, Juhani; Saarela, Aleksi An analysis and a reproof of Hmelevskii’s theorem. (Extended abstract). (English) Zbl 1161.68706 Ito, Masami (ed.) et al., Developments in language theory. 12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85779-2/pbk). Lecture Notes in Computer Science 5257, 467-478 (2008). MSC: 68R15 PDFBibTeX XMLCite \textit{J. Karhumäki} and \textit{A. Saarela}, Lect. Notes Comput. Sci. 5257, 467--478 (2008; Zbl 1161.68706) Full Text: DOI
Holub, Štěpán; Kortelainen, Juha On systems of word equations with simple loop sets. (English) Zbl 1185.68505 Theor. Comput. Sci. 380, No. 3, 363-372 (2007). MSC: 68R15 PDFBibTeX XMLCite \textit{Š. Holub} and \textit{J. Kortelainen}, Theor. Comput. Sci. 380, No. 3, 363--372 (2007; Zbl 1185.68505) Full Text: DOI
Holt, Derek F.; Röver, Claas E. Groups with indexed co-word problem. (English) Zbl 1151.20028 Int. J. Algebra Comput. 16, No. 5, 985-1014 (2006). MSC: 20F10 68Q45 03D40 20F05 PDFBibTeX XMLCite \textit{D. F. Holt} and \textit{C. E. Röver}, Int. J. Algebra Comput. 16, No. 5, 985--1014 (2006; Zbl 1151.20028) Full Text: DOI
Cleary, Sean; Elder, Murray; Taback, Jennifer Cone types and geodesic languages for lamplighter groups and Thompson’s group \(F\). (English) Zbl 1115.20032 J. Algebra 303, No. 2, 476-500 (2006). Reviewer: Y. Kobayashi (Funabashi) MSC: 20F65 20F06 20F05 68Q45 PDFBibTeX XMLCite \textit{S. Cleary} et al., J. Algebra 303, No. 2, 476--500 (2006; Zbl 1115.20032) Full Text: DOI arXiv
Ruohonen, Keijo Explicit test sets for iterated morphisms in free monoids and metabelian groups. (English) Zbl 1078.68094 Theor. Comput. Sci. 330, No. 1, 171-191 (2005). MSC: 68Q45 68Q70 20M35 20F10 PDFBibTeX XMLCite \textit{K. Ruohonen}, Theor. Comput. Sci. 330, No. 1, 171--191 (2005; Zbl 1078.68094) Full Text: DOI
Harju, Tero; Karhumäki, Juhani Many aspects of defect theorems. (English) Zbl 1078.68083 Theor. Comput. Sci. 324, No. 1, 35-54 (2004). MSC: 68Q45 68R15 PDFBibTeX XMLCite \textit{T. Harju} and \textit{J. Karhumäki}, Theor. Comput. Sci. 324, No. 1, 35--54 (2004; Zbl 1078.68083) Full Text: DOI
Katsura, Masashi; Kobayashi, Yuji; Otto, Friedrich Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions. (English) Zbl 1053.68055 Theor. Comput. Sci. 301, No. 1-3, 79-101 (2003). MSC: 68Q42 68Q05 20M05 03D35 PDFBibTeX XMLCite \textit{M. Katsura} et al., Theor. Comput. Sci. 301, No. 1--3, 79--101 (2003; Zbl 1053.68055) Full Text: DOI
Kobayashi, Yuji; Otto, Friedrich For finitely presented monoids the homological finiteness conditions FHT and \(\text{bi-FP}_3\) coincide. (English) Zbl 1028.20041 J. Algebra 264, No. 2, 327-341 (2003). Reviewer: Peeter Normak (Tallinn) MSC: 20M50 20M05 20M25 68Q42 PDFBibTeX XMLCite \textit{Y. Kobayashi} and \textit{F. Otto}, J. Algebra 264, No. 2, 327--341 (2003; Zbl 1028.20041) Full Text: DOI
Karhumäki, Juhani; Maňuch, Ján Multiple factorizations of words and defect effect. (English) Zbl 0996.68145 Theor. Comput. Sci. 273, No. 1-2, 81-97 (2002). MSC: 68R15 PDFBibTeX XMLCite \textit{J. Karhumäki} and \textit{J. Maňuch}, Theor. Comput. Sci. 273, No. 1--2, 81--97 (2002; Zbl 0996.68145) Full Text: DOI
Polák, Libor A solution of the word problem for free \(^*\)-regular semigroups. (English) Zbl 0981.20048 J. Pure Appl. Algebra 157, No. 1, 107-114 (2001). Reviewer: M.Guţan (Aubière) MSC: 20M05 68Q42 PDFBibTeX XMLCite \textit{L. Polák}, J. Pure Appl. Algebra 157, No. 1, 107--114 (2001; Zbl 0981.20048) Full Text: DOI
Kobayashi, Yuji Finite homotopy bases of one-relator monoids. (English) Zbl 0961.20045 J. Algebra 229, No. 2, 547-569 (2000). Reviewer: P.Normak (Tallinn) MSC: 20M05 20M50 68Q42 55Q05 55P99 PDFBibTeX XMLCite \textit{Y. Kobayashi}, J. Algebra 229, No. 2, 547--569 (2000; Zbl 0961.20045) Full Text: DOI
Karhumäki, Juhani; Plandowski, Wojciech; Mignosi, Filippo The expressibility of languages and relations by word equations. (English) Zbl 1401.68163 Degano, Pierpaolo (ed.) et al., Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7–11, 1997. Proceedings. Berlin: Springer-Verlag (ISBN 978-3-540-63165-1/pbk; 978-3-540-69194-5/ebook). Lecture Notes in Computer Science 1256, 98-109 (1997). MSC: 68Q45 68R15 PDFBibTeX XMLCite \textit{J. Karhumäki} et al., Lect. Notes Comput. Sci. 1256, 98--109 (1997; Zbl 1401.68163) Full Text: DOI
Choffrut, C.; Harju, T.; Karhumäki, J. A note on decidability questions on presentations of word semigroups. (English) Zbl 0901.68096 Theor. Comput. Sci. 183, No. 1, 83-92 (1997). MSC: 68Q45 PDFBibTeX XMLCite \textit{C. Choffrut} et al., Theor. Comput. Sci. 183, No. 1, 83--92 (1997; Zbl 0901.68096) Full Text: DOI