Lohrey, Markus Complexity of word problems for HNN-extensions. (English) Zbl 07677371 J. Comput. Syst. Sci. 135, 145-157 (2023). MSC: 68-XX PDFBibTeX XMLCite \textit{M. Lohrey}, J. Comput. Syst. Sci. 135, 145--157 (2023; Zbl 07677371) Full Text: DOI
Gebhardt, Kilian; Meunier, Frédéric; Salvati, Sylvain \(O_n\) is an \(n\)-MCFL. (English) Zbl 1483.68169 J. Comput. Syst. Sci. 127, 41-52 (2022). MSC: 68Q45 20F10 PDFBibTeX XMLCite \textit{K. Gebhardt} et al., J. Comput. Syst. Sci. 127, 41--52 (2022; Zbl 1483.68169) Full Text: DOI arXiv
Chan, Timothy M.; He, Qizheng More on change-making and related problems. (English) Zbl 1491.68126 J. Comput. Syst. Sci. 124, 159-169 (2022). Reviewer: Roberto Solis-Oba (London) MSC: 68R05 11D07 68Q25 68W05 68W32 68W40 90C27 90C39 PDFBibTeX XMLCite \textit{T. M. Chan} and \textit{Q. He}, J. Comput. Syst. Sci. 124, 159--169 (2022; Zbl 1491.68126) Full Text: DOI arXiv Link
Jeż, Artur Word equations in non-deterministic linear space. (English) Zbl 1472.68068 J. Comput. Syst. Sci. 123, 122-142 (2022). MSC: 68Q25 68P30 68Q45 PDFBibTeX XMLCite \textit{A. Jeż}, J. Comput. Syst. Sci. 123, 122--142 (2022; Zbl 1472.68068) Full Text: DOI Link
Berlinkov, Mikhail V.; Ferens, Robert; Szykuła, Marek Preimage problems for deterministic finite automata. (English) Zbl 1464.68148 J. Comput. Syst. Sci. 115, 214-234 (2021). MSC: 68Q45 PDFBibTeX XMLCite \textit{M. V. Berlinkov} et al., J. Comput. Syst. Sci. 115, 214--234 (2021; Zbl 1464.68148) Full Text: DOI arXiv
Ramaswamy, Vidhya; Sarma, Jayalal; Sunil, K. S. Space complexity of reachability testing in labelled graphs. (English) Zbl 1425.68322 J. Comput. Syst. Sci. 105, 40-53 (2019). MSC: 68R10 05C25 05C78 68Q17 68Q25 PDFBibTeX XMLCite \textit{V. Ramaswamy} et al., J. Comput. Syst. Sci. 105, 40--53 (2019; Zbl 1425.68322) Full Text: DOI
Vorel, Vojtěch; Roman, Adam Complexity of road coloring with prescribed reset words. (English) Zbl 1425.68236 J. Comput. Syst. Sci. 104, 342-358 (2019). MSC: 68Q45 05C15 68Q25 PDFBibTeX XMLCite \textit{V. Vorel} and \textit{A. Roman}, J. Comput. Syst. Sci. 104, 342--358 (2019; Zbl 1425.68236) Full Text: DOI arXiv
Potapov, Igor; Semukhin, Pavel Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\). (English) Zbl 1421.68095 J. Comput. Syst. Sci. 100, 30-43 (2019). MSC: 68Q45 15A30 20M05 20M35 PDFBibTeX XMLCite \textit{I. Potapov} and \textit{P. Semukhin}, J. Comput. Syst. Sci. 100, 30--43 (2019; Zbl 1421.68095) Full Text: DOI
Jain, Sanjay; Miasnikov, Alexei; Stephan, Frank The complexity of verbal languages over groups. (English) Zbl 1412.68132 J. Comput. Syst. Sci. 101, 68-85 (2019). MSC: 68Q45 20F10 68Q70 PDFBibTeX XMLCite \textit{S. Jain} et al., J. Comput. Syst. Sci. 101, 68--85 (2019; Zbl 1412.68132) Full Text: DOI
Okhotin, Alexander; Salomaa, Kai State complexity of operations on input-driven pushdown automata. (English) Zbl 1370.68186 J. Comput. Syst. Sci. 86, 207-228 (2017). MSC: 68Q45 PDFBibTeX XMLCite \textit{A. Okhotin} and \textit{K. Salomaa}, J. Comput. Syst. Sci. 86, 207--228 (2017; Zbl 1370.68186) Full Text: DOI
Woryna, Adam On groups generated by bi-reversible automata: the two-state case over a changing alphabet. (English) Zbl 1370.68193 J. Comput. Syst. Sci. 86, 181-190 (2017). MSC: 68Q45 20F10 PDFBibTeX XMLCite \textit{A. Woryna}, J. Comput. Syst. Sci. 86, 181--190 (2017; Zbl 1370.68193) Full Text: DOI arXiv
Manea, Florin; Müller, Mike; Nowotka, Dirk; Seki, Shinnosuke The extended equation of Lyndon and Schützenberger. (English) Zbl 1428.68226 J. Comput. Syst. Sci. 85, 132-167 (2017). MSC: 68R15 PDFBibTeX XMLCite \textit{F. Manea} et al., J. Comput. Syst. Sci. 85, 132--167 (2017; Zbl 1428.68226) Full Text: DOI
Badkobeh, Golnaz; Crochemore, Maxime Computing maximal-exponent factors in an overlap-free word. (English) Zbl 1333.68303 J. Comput. Syst. Sci. 82, No. 3, 477-487 (2016). MSC: 68W32 68Q45 68R15 PDFBibTeX XMLCite \textit{G. Badkobeh} and \textit{M. Crochemore}, J. Comput. Syst. Sci. 82, No. 3, 477--487 (2016; Zbl 1333.68303) Full Text: DOI Link
Becher, Verónica; Carton, Olivier; Heiber, Pablo Ariel Normality and automata. (English) Zbl 1329.68156 J. Comput. Syst. Sci. 81, No. 8, 1592-1613 (2015). Reviewer: Andreas Maletti (Stuttgart) MSC: 68Q45 68Q10 PDFBibTeX XMLCite \textit{V. Becher} et al., J. Comput. Syst. Sci. 81, No. 8, 1592--1613 (2015; Zbl 1329.68156) Full Text: DOI
Salvati, Sylvain MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies. (English) Zbl 1325.68133 J. Comput. Syst. Sci. 81, No. 7, 1252-1277 (2015). Reviewer: Fabienne Chouraqui (Haifa) MSC: 68Q45 20F05 20F10 PDFBibTeX XMLCite \textit{S. Salvati}, J. Comput. Syst. Sci. 81, No. 7, 1252--1277 (2015; Zbl 1325.68133) Full Text: DOI
Fernau, Henning; Heggernes, Pinar; Villanger, Yngve A multi-parameter analysis of hard problems on deterministic finite automata. (English) Zbl 1320.68090 J. Comput. Syst. Sci. 81, No. 4, 747-765 (2015). MSC: 68Q17 68Q45 PDFBibTeX XMLCite \textit{H. Fernau} et al., J. Comput. Syst. Sci. 81, No. 4, 747--765 (2015; Zbl 1320.68090) Full Text: DOI
Alazemi, Hamed M. K.; Černý, Anton Several extensions of the Parikh matrix \(L\)-morphism. (English) Zbl 1285.68125 J. Comput. Syst. Sci. 79, No. 5, 658-668 (2013). MSC: 68R15 PDFBibTeX XMLCite \textit{H. M. K. Alazemi} and \textit{A. Černý}, J. Comput. Syst. Sci. 79, No. 5, 658--668 (2013; Zbl 1285.68125) Full Text: DOI
Crochemore, M.; Iliopoulos, C. S.; Kubica, M.; Radoszewski, J.; Rytter, W.; Waleń, T. The maximal number of cubic runs in a word. (English) Zbl 1250.68217 J. Comput. Syst. Sci. 78, No. 6, 1828-1836 (2012). MSC: 68R15 68Q45 PDFBibTeX XMLCite \textit{M. Crochemore} et al., J. Comput. Syst. Sci. 78, No. 6, 1828--1836 (2012; Zbl 1250.68217) Full Text: DOI
Charlier, Émilie; Le Gonidec, Marion; Rigo, Michel Representing real numbers in a generalized numeration system. (English) Zbl 1215.68119 J. Comput. Syst. Sci. 77, No. 4, 743-759 (2011). MSC: 68Q45 11A67 PDFBibTeX XMLCite \textit{É. Charlier} et al., J. Comput. Syst. Sci. 77, No. 4, 743--759 (2011; Zbl 1215.68119) Full Text: DOI
Herbst, Thomas Some remarks on a theorem of Sakarovitch. (English) Zbl 0743.68086 J. Comput. Syst. Sci. 44, No. 1, 160-165 (1992). MSC: 68Q45 PDFBibTeX XMLCite \textit{T. Herbst}, J. Comput. Syst. Sci. 44, No. 1, 160--165 (1992; Zbl 0743.68086) Full Text: DOI
Garzon, Max; Zalcstein, Yechezkel On isomorphism testing of a class of 2-nilpotent groups. (English) Zbl 0749.20018 J. Comput. Syst. Sci. 42, No. 2, 237-248 (1991). Reviewer: N.Ya.Medvedev (Barnaul) MSC: 20F10 68Q25 20D15 20F05 PDFBibTeX XMLCite \textit{M. Garzon} and \textit{Y. Zalcstein}, J. Comput. Syst. Sci. 42, No. 2, 237--248 (1991; Zbl 0749.20018) Full Text: DOI
Otto, Friedrich; Wrathall, Celia Overlaps in free partially commutative monoids. (English) Zbl 0719.20030 J. Comput. Syst. Sci. 42, No. 2, 186-198 (1991). Reviewer: F.Otto (Kassel) MSC: 20M05 68Q10 68R15 20M35 68W30 PDFBibTeX XMLCite \textit{F. Otto} and \textit{C. Wrathall}, J. Comput. Syst. Sci. 42, No. 2, 186--198 (1991; Zbl 0719.20030) Full Text: DOI
Barrington, David A. Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\). (English) Zbl 0667.68059 J. Comput. Syst. Sci. 38, No. 1, 150-164 (1989). Reviewer: Ch.Meinel MSC: 68Q25 68Q05 20F10 PDFBibTeX XMLCite \textit{D. A. Barrington}, J. Comput. Syst. Sci. 38, No. 1, 150--164 (1989; Zbl 0667.68059) Full Text: DOI
Katsura, Masashi Automorphism groups and factor automata of strongly connected automata. (English) Zbl 0656.68058 J. Comput. Syst. Sci. 36, No. 1, 25-65 (1988). Reviewer: M.Demlová MSC: 68Q70 20B25 20F10 PDFBibTeX XMLCite \textit{M. Katsura}, J. Comput. Syst. Sci. 36, No. 1, 25--65 (1988; Zbl 0656.68058) Full Text: DOI
Otto, Friedrich On deciding the confluence of a finite string-rewriting system on a given congruence class. (English) Zbl 0645.03033 J. Comput. Syst. Sci. 35, 285-310 (1987). Reviewer: F.Otto MSC: 03D03 03D40 68Q99 20M05 PDFBibTeX XMLCite \textit{F. Otto}, J. Comput. Syst. Sci. 35, 285--310 (1987; Zbl 0645.03033) Full Text: DOI
Cosmadakis, Stavros S.; Kanellakis, Paris C. Partition semantics for relations. (English) Zbl 0625.68073 J. Comput. Syst. Sci. 33, 203-233 (1986). MSC: 68P20 06B25 PDFBibTeX XMLCite \textit{S. S. Cosmadakis} and \textit{P. C. Kanellakis}, J. Comput. Syst. Sci. 33, 203--233 (1986; Zbl 0625.68073) Full Text: DOI
Muller, David E.; Schupp, Paul E. Groups, the theory of ends, and context-free languages. (English) Zbl 0537.20011 J. Comput. Syst. Sci. 26, 295-310 (1983). Reviewer: A.V.Anisimov MSC: 20F05 68Q45 20F10 20E05 PDFBibTeX XMLCite \textit{D. E. Muller} and \textit{P. E. Schupp}, J. Comput. Syst. Sci. 26, 295--310 (1983; Zbl 0537.20011) Full Text: DOI
Luks, Eugene M. Isomorphism of graphs of bounded valence can be tested in polynomial time. (English) Zbl 0493.68064 J. Comput. Syst. Sci. 25, 42-65 (1982). MSC: 68R10 05C25 20B25 20F10 68Q25 05C15 PDFBibTeX XMLCite \textit{E. M. Luks}, J. Comput. Syst. Sci. 25, 42--65 (1982; Zbl 0493.68064) Full Text: DOI
Ruohonen, Keijo The decidability of the DOL-DTOL equivalence problem. (English) Zbl 0491.68048 J. Comput. Syst. Sci. 22, 42-52 (1981). MSC: 68Q42 68Q45 03D40 68Q25 PDFBibTeX XMLCite \textit{K. Ruohonen}, J. Comput. Syst. Sci. 22, 42--52 (1981; Zbl 0491.68048) Full Text: DOI
Lynch, Nancy A. Straight-line program length as a parameter for complexity analysis. (English) Zbl 0458.68008 J. Comput. Syst. Sci. 21, 251-280 (1980). MSC: 68Q25 08A50 20F10 PDFBibTeX XMLCite \textit{N. A. Lynch}, J. Comput. Syst. Sci. 21, 251--280 (1980; Zbl 0458.68008) Full Text: DOI
Lynch, Nancy Approximations to the halting problem. (English) Zbl 0299.02042 J. Comput. Syst. Sci. 9, 143-150 (1974). MSC: 03D10 03D25 03B25 03D40 PDFBibTeX XMLCite \textit{N. Lynch}, J. Comput. Syst. Sci. 9, 143--150 (1974; Zbl 0299.02042) Full Text: DOI
Hughes, C. E. Many-one degrees associated with semi-Thue systems. (English) Zbl 0284.02020 J. Comput. Syst. Sci. 7, 497-505 (1973). MSC: 03D30 03D03 03D40 PDFBibTeX XMLCite \textit{C. E. Hughes}, J. Comput. Syst. Sci. 7, 497--505 (1973; Zbl 0284.02020) Full Text: DOI