Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai Deciding path size of nondeterministic (and input-driven) pushdown automata. (English) Zbl 07619402 Theor. Comput. Sci. 939, 170-181 (2023). MSC: 68Q45 PDFBibTeX XMLCite \textit{Y.-S. Han} et al., Theor. Comput. Sci. 939, 170--181 (2023; Zbl 07619402) Full Text: DOI
Han, Yo-Sub; Ko, Sang-Ki; Ng, Timothy; Salomaa, Kai Consensus string problem for multiple regular languages. (English) Zbl 1497.68269 Inf. Comput. 279, Article ID 104615, 9 p. (2021). MSC: 68Q45 68Q17 68Q25 PDFBibTeX XMLCite \textit{Y.-S. Han} et al., Inf. Comput. 279, Article ID 104615, 9 p. (2021; Zbl 1497.68269) Full Text: DOI
Okhotin, Alexander; Salomaa, Kai State complexity of the quotient operation on input-driven pushdown automata. (English) Zbl 1427.68152 Int. J. Found. Comput. Sci. 30, No. 6-7, 1217-1235 (2019). MSC: 68Q45 PDFBibTeX XMLCite \textit{A. Okhotin} and \textit{K. Salomaa}, Int. J. Found. Comput. Sci. 30, No. 6--7, 1217--1235 (2019; Zbl 1427.68152) Full Text: DOI
Okhotin, Alexander; Salomaa, Kai Further closure properties of input-driven pushdown automata. (English) Zbl 1435.68179 Theor. Comput. Sci. 798, 65-77 (2019). MSC: 68Q45 PDFBibTeX XMLCite \textit{A. Okhotin} and \textit{K. Salomaa}, Theor. Comput. Sci. 798, 65--77 (2019; Zbl 1435.68179) Full Text: DOI Link
Okhotin, Alexander; Salomaa, Kai Edit distance neighbourhoods of input-driven pushdown automata. (English) Zbl 1423.68262 Theor. Comput. Sci. 777, 417-430 (2019). MSC: 68Q45 PDFBibTeX XMLCite \textit{A. Okhotin} and \textit{K. Salomaa}, Theor. Comput. Sci. 777, 417--430 (2019; Zbl 1423.68262) Full Text: DOI
Okhotin, Alexander; Salomaa, Kai Edit distance neighbourhoods of input-driven pushdown automata. (English) Zbl 1489.68133 Weil, Pascal (ed.), Computer science – theory and applications. 12th international computer science symposium in Russia, CSR 2017, Kazan, Russia, June 8–12, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10304, 260-272 (2017). MSC: 68Q45 PDFBibTeX XMLCite \textit{A. Okhotin} and \textit{K. Salomaa}, Lect. Notes Comput. Sci. 10304, 260--272 (2017; Zbl 1489.68133) Full Text: DOI
Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. Worst case branching and other measures of nondeterminism. (English) Zbl 1371.68163 Int. J. Found. Comput. Sci. 28, No. 3, 195-210 (2017). MSC: 68Q45 PDFBibTeX XMLCite \textit{A. Palioudakis} et al., Int. J. Found. Comput. Sci. 28, No. 3, 195--210 (2017; Zbl 1371.68163) 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
Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai State complexity of deletion and bipolar deletion. (English) Zbl 1335.68121 Acta Inf. 53, No. 1, 67-85 (2016). MSC: 68Q45 PDFBibTeX XMLCite \textit{Y.-S. Han} et al., Acta Inf. 53, No. 1, 67--85 (2016; Zbl 1335.68121) Full Text: DOI Link
Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G. Operational state complexity of unary NFAs with finite nondeterminism. (English) Zbl 1332.68125 Theor. Comput. Sci. 610, Part A, 108-120 (2016). MSC: 68Q45 PDFBibTeX XMLCite \textit{A. Palioudakis} et al., Theor. Comput. Sci. 610, Part A, 108--120 (2016; Zbl 1332.68125) Full Text: DOI
Eom, Hae-Sung; Han, Yo-Sub; Salomaa, Kai State complexity of \(k\)-union and \(k\)-intersection for prefix-free regular languages. (English) Zbl 1327.68155 Int. J. Found. Comput. Sci. 26, No. 2, 211-227 (2015). Reviewer: Magnus Steinby (Turku) MSC: 68Q45 PDFBibTeX XMLCite \textit{H.-S. Eom} et al., Int. J. Found. Comput. Sci. 26, No. 2, 211--227 (2015; Zbl 1327.68155) Full Text: DOI
Okhotin, Alexander; Salomaa, Kai Descriptional complexity of unambiguous input-driven pushdown automata. (English) Zbl 1318.68111 Theor. Comput. Sci. 566, 1-11 (2015). MSC: 68Q45 PDFBibTeX XMLCite \textit{A. Okhotin} and \textit{K. Salomaa}, Theor. Comput. Sci. 566, 1--11 (2015; Zbl 1318.68111) Full Text: DOI
Salomaa, Arto; Salomaa, Kai; Yu, Sheng Undecidability of state complexity. (English) Zbl 1401.68167 Int. J. Comput. Math. 90, No. 6, 1310-1320 (2013). Reviewer: Michal Kunc (Brno) MSC: 68Q45 PDFBibTeX XMLCite \textit{A. Salomaa} et al., Int. J. Comput. Math. 90, No. 6, 1310--1320 (2013; Zbl 1401.68167) Full Text: DOI
Okhotin, Alexander; Piao, Xiaoxue; Salomaa, Kai Descriptional complexity of input-driven pushdown automata. (English) Zbl 1367.68176 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, 186-206 (2012). MSC: 68Q45 PDFBibTeX XMLCite \textit{A. Okhotin} et al., Lect. Notes Comput. Sci. 7300, 186--206 (2012; Zbl 1367.68176) Full Text: DOI
Piao, Xiaoxue; Salomaa, Kai Lower bounds for the size of deterministic unranked tree automata. (English) Zbl 1257.68099 Theor. Comput. Sci. 454, 231-239 (2012). Reviewer: Magnus Steinby (Turku) MSC: 68Q45 PDFBibTeX XMLCite \textit{X. Piao} and \textit{K. Salomaa}, Theor. Comput. Sci. 454, 231--239 (2012; Zbl 1257.68099) Full Text: DOI
Piao, Xiaoxue; Salomaa, Kai State complexity of Kleene-star operations on trees. (English) Zbl 1353.68171 Dinneen, Michael J. (ed.) et al., Computation, physics and beyond. International workshop on theoretical computer science, WTCS 2012, dedicated to Cristian S. Calude on the occasion of his 60th birthday, Auckland, New Zealand, February 21–24, 2012. Revised selected and invited papers. Berlin: Springer (ISBN 978-3-642-27653-8/pbk). Lecture Notes in Computer Science 7160, 388-402 (2012). MSC: 68Q45 PDFBibTeX XMLCite \textit{X. Piao} and \textit{K. Salomaa}, Lect. Notes Comput. Sci. 7160, 388--402 (2012; Zbl 1353.68171) Full Text: DOI
Piao, Xiaoxue; Salomaa, Kai State complexity of the concatenation of regular tree languages. (English) Zbl 1238.68079 Theor. Comput. Sci. 429, 273-281 (2012). MSC: 68Q45 PDFBibTeX XMLCite \textit{X. Piao} and \textit{K. Salomaa}, Theor. Comput. Sci. 429, 273--281 (2012; Zbl 1238.68079) Full Text: DOI
Piao, Xiaoxue; Salomaa, Kai State trade-offs in unranked tree automata. (English) Zbl 1341.68106 Holzer, Markus (ed.) et al., Descriptional complexity of formal systems. 13th international workshop, DCFS 2011, Gießen/Limburg, Germany, July 25–27, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22599-4/pbk). Lecture Notes in Computer Science 6808, 261-274 (2011). MSC: 68Q45 PDFBibTeX XMLCite \textit{X. Piao} and \textit{K. Salomaa}, Lect. Notes Comput. Sci. 6808, 261--274 (2011; Zbl 1341.68106) Full Text: DOI
Domaratzki, Michael; Salomaa, Kai On language decompositions and primality. (English) Zbl 1327.68154 Calude, Cristian S. (ed.) et al., Rainbow of computer science. Dedicated to Hermann Maurer on the occasion of his 70th birthday. Berlin: Springer (ISBN 978-3-642-19390-3/pbk). Lecture Notes in Computer Science 6570, 63-75 (2011). MSC: 68Q45 PDFBibTeX XMLCite \textit{M. Domaratzki} and \textit{K. Salomaa}, Lect. Notes Comput. Sci. 6570, 63--75 (2011; Zbl 1327.68154) Full Text: DOI
Salomaa, Kai; Yu, Sheng; Zan, Jinfeng Deciding determinism of caterpillar expressions. (English) Zbl 1194.68146 Theor. Comput. Sci. 410, No. 37, 3438-3446 (2009). MSC: 68Q45 PDFBibTeX XMLCite \textit{K. Salomaa} et al., Theor. Comput. Sci. 410, No. 37, 3438--3446 (2009; Zbl 1194.68146) Full Text: DOI
Salomaa, Kai; Yu, Sheng; Zan, Jinfeng Deterministic caterpillar expressions. (English) Zbl 1139.68374 Holub, Jan (ed.) et al., Implementation and application of automata. 12th international conference, CIAA 2007, Prague, Czech Republic, July 16–18, 2007. Revised selected papers. Berlin: Springer (ISBN 978-3-540-76335-2/pbk). Lecture Notes in Computer Science 4783, 97-108 (2007). MSC: 68Q45 PDFBibTeX XMLCite \textit{K. Salomaa} et al., Lect. Notes Comput. Sci. 4783, 97--108 (2007; Zbl 1139.68374) Full Text: DOI
Domaratzki, Michael; Salomaa, Kai Decidability of trajectory-based equations. (English) Zbl 1079.68049 Theor. Comput. Sci. 345, No. 2-3, 304-330 (2005). MSC: 68Q45 PDFBibTeX XMLCite \textit{M. Domaratzki} and \textit{K. Salomaa}, Theor. Comput. Sci. 345, No. 2--3, 304--330 (2005; Zbl 1079.68049) Full Text: DOI