Publications
2024
Reachability in Linear Recurrence Automata
Hirvensalo, M., Kawamura, A., Potapov, I., & Yuyama, T. (2024). Reachability in Linear Recurrence Automata. In Unknown Conference (pp. 167-183). Springer Nature Switzerland. doi:10.1007/978-3-031-72621-7_12
Brief Announcement: Collision-Free Robot Scheduling
Adamson, D., Flaherty, N., Potapov, I., & Spirakis, P. G. (2024). Brief Announcement: Collision-Free Robot Scheduling. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 292. doi:10.4230/LIPIcs.SAND.2024.22
Structural and Combinatorial Properties of 2-Swap Word Permutation Graphs.
Adamson, D., Flaherty, N., Potapov, I., & Spirakis, P. G. (2024). Structural and Combinatorial Properties of 2-Swap Word Permutation Graphs.. In J. A. Soto, & A. Wiese (Eds.), LATIN (2) Vol. 14579 (pp. 61-76). Springer. Retrieved from https://doi.org/10.1007/978-3-031-55601-2
Structural and Combinatorial Properties of 2-Swap Word Permutation Graphs
Adamson, D., Flaherty, N., Potapov, I., & Spirakis, P. G. (2024). Structural and Combinatorial Properties of 2-Swap Word Permutation Graphs. Unknown Journal, 61-76. doi:10.1007/978-3-031-55601-2_5
2023
The membership problem for subsemigroups of GL2(Z) is NP-complete.
Bell, P. C., Hirvensalo, M., & Potapov, I. (2023). The membership problem for subsemigroups of GL2(Z) is NP-complete.. Information and Computation, 296, 105132. doi:10.1016/j.ic.2023.105132
Preface
Bell, P. C., Potapov, I., Schmitz, S., & Totzke, P. (2023). Preface. Fundamenta Informaticae, 189(3-4), i-iii. doi:10.3233/fi-222158
On the Identity and Group Problems for Complex Heisenberg Matrices
Bell, P. C., Niskanen, R., Potapov, I., & Semukhin, P. (2023). On the Identity and Group Problems for Complex Heisenberg Matrices. In Unknown Conference (pp. 42-55). Springer Nature Switzerland. doi:10.1007/978-3-031-45286-4_4
Reinforcement Learning in Crystal Structure Prediction
Zamaraeva, E., Collins, C. M., Antypov, D., Gusev, V. V., Savani, R., Dyer, M. S., . . . Spirakis, P. G. (n.d.). Reinforcement Learning in Crystal Structure Prediction. Digital Discovery. doi:10.1039/d3dd00063j
Optimality Guarantees for Crystal Structure Prediction
Adamson, D., Gusev, V. V., Deligkas, A., Antypov, D., Collins, C. M., Krysta, P., . . . Rosseinsky, M. J. (2023). Optimality Guarantees for Crystal Structure Prediction. Nature. doi:10.1038/s41586-023-06071-y
Reinforcement Learning in Crystal Structure Prediction
Integer Weighted Automata on Infinite Words
Halava, V., Harju, T., Niskanen, R., & Potapov, I. (2023). Integer Weighted Automata on Infinite Words. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 34(02N03), 163-182. doi:10.1142/S0129054122440014
Distributed transformations of Hamiltonian shapes based on line moves
Almethen, A., Michail, O., & Potapov, I. (2023). Distributed transformations of Hamiltonian shapes based on line moves. THEORETICAL COMPUTER SCIENCE, 942, 142-168. doi:10.1016/j.tcs.2022.11.029
On the Identity and Group Problems for Complex Heisenberg Matrices.
Bell, P. C., Niskanen, R., Potapov, I., & Semukhin, P. (2023). On the Identity and Group Problems for Complex Heisenberg Matrices.. CoRR, abs/2307.05283.
Preface
Bournez, O., Formenti, E., & Potapov, I. (2023). Preface (Vol. 14235 LNCS).
Reachability Problems - 17th International Conference, RP 2023, Nice, France, October 11-13, 2023, Proceedings
Bournez, O., Formenti, E., & Potapov, I. (Eds.) (2023). Reachability Problems - 17th International Conference, RP 2023, Nice, France, October 11-13, 2023, Proceedings. In RP Vol. 14235. Springer.
The k-Centre Problem for Classes of Cyclic Words
Adamson, D., Deligkas, A., Gusev, V. V., & Potapov, I. (2023). The k-Centre Problem for Classes of Cyclic Words. In SOFSEM 2023: THEORY AND PRACTICE OF COMPUTER SCIENCE Vol. 13878 (pp. 385-400). doi:10.1007/978-3-031-23101-8_26
2022
Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach
Connor, M., Michail, O., & Potapov, I. (2022). Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach. THEORETICAL COMPUTER SCIENCE, 936, 77-91. doi:10.1016/j.tcs.2022.09.016
The Complexity of Periodic Energy Minimisation
Adamson, D., Deligkas, A., Gusev, V. V., & Potapov, I. (2022). The Complexity of Periodic Energy Minimisation. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 241. doi:10.4230/LIPIcs.MFCS.2022.8
A Geometric Approach to Passive Localisation
Triommatis, T., Potapov, I., Rees, G., & Ralph, J. F. (2022). A Geometric Approach to Passive Localisation. In 2022 25TH INTERNATIONAL CONFERENCE ON INFORMATION FUSION (FUSION 2022). Retrieved from https://www.webofscience.com/
Towards Uniform Online Spherical Tessellations
Bell, P. C., & Potapov, I. (n.d.). Towards Uniform Online Spherical Tessellations. In Discrete and Computational Geometry: an international journal of mathematics and computer science. Springer Nature. doi:10.1007/s00454-022-00384-x
Optimizing reachability sets in temporal graphs by delaying
Deligkas, A., & Potapov, I. (2022). Optimizing reachability sets in temporal graphs by delaying. INFORMATION AND COMPUTATION, 285. doi:10.1016/j.ic.2022.104890
Towards Uniform Online Spherical Tessellations.
Bell, P. C., & Potapov, I. (2022). Towards Uniform Online Spherical Tessellations.. Discret. Comput. Geom., 67, 1124-1146.
Optimizing reachability sets in temporal graphs by delaying
Deligkas, A., & Potapov, I. (2022). Optimizing reachability sets in temporal graphs by delaying. Information and Computation, 104890. doi:10.1016/j.ic.2022.104890
On the Hardness of Energy Minimisation for Crystal Structure Prediction
Adamson, D., Deligkas, A., Gusev, V. V., & Potapov, I. (2021). On the Hardness of Energy Minimisation for Crystal Structure Prediction. FUNDAMENTA INFORMATICAE, 184(3), 181-203. doi:10.3233/FI-2021-2096
On efficient connectivity-preserving transformations in a grid
Almethen, A., Michail, O., & Potapov, I. (2022). On efficient connectivity-preserving transformations in a grid. THEORETICAL COMPUTER SCIENCE, 898, 132-148. doi:10.1016/j.tcs.2021.11.004
Preface
Lin, A. W., Zetzsche, G., & Potapov, I. (2022). Preface (Vol. 13608 LNCS).
Preface.
Bell, P. C., Potapov, I., Schmitz, S., & Totzke, P. (2022). Preface.. Fundam. Informaticae, 189.
2021
Reachability problems in low-dimensional nondeterministic polynomial maps over integers
Ko, S. K., Niskanen, R., & Potapov, I. (2021). Reachability problems in low-dimensional nondeterministic polynomial maps over integers. INFORMATION AND COMPUTATION, 281. doi:10.1016/j.ic.2021.104785
Ranking Bracelets in Polynomial Time
Ranking bracelets in polynomial time
Adamson, D., Deligkas, A., Gusev, V. V., & Potapov, I. (2021). Ranking Bracelets in Polynomial Time. Retrieved from http://arxiv.org/abs/2104.04324v1
Preface
Bojanczyk, M., Brihaye, T., Haase, C., Lasota, S., Ouaknine, J., & Potapov, I. (2021). Preface. INFORMATION AND COMPUTATION, 277. doi:10.1016/j.ic.2020.104579
On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond
Bell, P. C., Potapov, I., & Semukhin, P. (2021). On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond. Information and Computation, 104736. doi:10.1016/j.ic.2021.104736
Preface.
Hague, M., & Potapov, I. (2021). Preface.. Fundam. Informaticae, 178. doi:10.3233/FI-2021-1995
Special Issue on the 11th International Workshop on Reachability Problems (RP 2017) Preface
Hague, M., & Potapov, I. (2021). Special Issue on the 11th International Workshop on Reachability Problems (RP 2017) Preface. FUNDAMENTA INFORMATICAE, 178(1-2), V-VI. doi:10.3233/FI-2021-1995
Centralised Connectivity-Preserving Transformations for Programmable Matter: A Minimal Seed Approach
Connor, M., Michail, O., & Potapov, I. (2021). Centralised Connectivity-Preserving Transformations for Programmable Matter: A Minimal Seed Approach. In ALGORITHMS FOR SENSOR SYSTEMS, ALGOSENSORS 2021 Vol. 12961 (pp. 45-60). doi:10.1007/978-3-030-89240-1_4
Distributed Transformations of Hamiltonian Shapes based on Line Moves
Almethen, A., Michail, O., & Potapov, I. (2021). Distributed Transformations of Hamiltonian Shapes Based on Line Moves. In ALGORITHMS FOR SENSOR SYSTEMS, ALGOSENSORS 2021 Vol. 12961 (pp. 1-16). doi:10.1007/978-3-030-89240-1_1
Integer Weighted Automata on Infinite Words
Halava, V., Harju, T., Niskanen, R., & PotapoV, I. (2021). Integer Weighted Automata on Infinite Words. In DEVELOPMENTS IN LANGUAGE THEORY, DLT 2021 Vol. 12811 (pp. 167-179). doi:10.1007/978-3-030-81508-0_14
Preface
Bell, P. C., Totzke, P., & Potapov, I. (2021). Preface (Vol. 13035 LNCS).
Preface.
Bojanczyk, M., Brihaye, T., Haase, C., Lasota, S., Ouaknine, J., & Potapov, I. (2021). Preface.. Inf. Comput., 277, 104579. doi:10.1016/j.ic.2020.104579
Ranking Bracelets in Polynomial Time.
Adamson, D., Gusev, V. V., Potapov, I., & Deligkas, A. (2021). Ranking Bracelets in Polynomial Time.. In P. Gawrychowski, & T. Starikovskaya (Eds.), CPM Vol. 191 (pp. 4:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from https://www.dagstuhl.de/dagpub/978-3-95977-186-3
2020
The K-Centre Problem for Necklaces
Adamson, D., Deligkas, A., Gusev, V. V., & Potapov, I. (2020). The K-Centre Problem for Necklaces. Retrieved from http://arxiv.org/abs/2005.10095v1
On Efficient Connectivity-Preserving Transformations in a Grid
Almethen, A., Michail, O., & Potapov, I. (2020). On Efficient Connectivity-Preserving Transformations in a Grid. ALGORITHMS FOR SENSOR SYSTEMS, ALGOSENSORS 2020, 12503, 76-91. doi:10.1007/978-3-030-62401-9_6
Optimizing Reachability Sets in Temporal Graphs by Delaying
Deligkas, A., & Potapov, I. (2020). Optimizing Reachability Sets in Temporal Graphs by Delaying. Retrieved from https://www.webofscience.com/
Optimizing Reachability Sets in Temporal Graphs by Delaying
Deligkas, A., & Potapov, I. (n.d.). Optimizing Reachability Sets in Temporal Graphs by Delaying. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 9810-9817. doi:10.1609/aaai.v34i06.6533
On decidability and complexity of low-dimensional robot games
Niskanen, R., Potapov, I., & Reichert, J. (2020). On decidability and complexity of low-dimensional robot games. Journal of Computer and System Sciences, 107, 124-141. doi:10.1016/j.jcss.2019.08.003
Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices.
Diekert, V., Potapov, I., & Semukhin, P. (2020). Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices.. In I. Z. Emiris, & L. Zhi (Eds.), ISSAC (pp. 122-129). ACM. Retrieved from https://doi.org/10.1145/3373207
On Efficient Connectivity-Preserving Transformations in a Grid.
Almethen, A., Michail, O., & Potapov, I. (2020). On Efficient Connectivity-Preserving Transformations in a Grid.. In C. M. Pinotti, A. Navarra, & A. Bagchi (Eds.), ALGOSENSORS Vol. 12503 (pp. 76-91). Springer. Retrieved from https://doi.org/10.1007/978-3-030-62401-9
On the Hardness of Energy Minimisation for Crystal Structure Prediction.
Adamson, D., Deligkas, A., Gusev, V. V., & Potapov, I. (2020). On the Hardness of Energy Minimisation for Crystal Structure Prediction.. In A. Chatzigeorgiou, R. Dondi, H. Herodotou, C. A. Kapoutsis, Y. Manolopoulos, G. A. Papadopoulos, & F. Sikora (Eds.), SOFSEM Vol. 12011 (pp. 587-596). Springer. Retrieved from https://doi.org/10.1007/978-3-030-38919-2
Preface
Schmitz, S., & Potapov, I. (2020). Preface. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12448 LNCS, vi-ix. doi:10.1142/S0129054118010013
Pushing lines helps: Efficient universal centralised transformations for programmable matter.
Almethen, A., Michail, O., & Potapov, I. (2020). Pushing lines helps: Efficient universal centralised transformations for programmable matter.. Theor. Comput. Sci., 830-831, 43-59. doi:10.1016/j.tcs.2020.04.026
Reachability Problems - 14th International Conference, RP 2020, Paris, France, October 19-21, 2020, Proceedings
Schmitz, S., & Potapov, I. (Eds.) (2020). Reachability Problems - 14th International Conference, RP 2020, Paris, France, October 19-21, 2020, Proceedings (Vol. 12448). Springer.
2019
Pushing Lines Helps: Efficient Universal Centralised Transformations for Programmable Matter
Almethen, A., Michail, O., & Potapov, I. (2019). Pushing Lines Helps: Efficient Universal Centralised Transformations for Programmable Matter. In International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS). doi:10.1007/978-3-030-34405-4_3
On the Hardness of Energy Minimisation for Crystal Structure Prediction
Adamson, D., Deligkas, A., Gusev, V. V., & Potapov, I. (2020). On the Hardness of Energy Minimisation for Crystal Structure Prediction. doi:10.1007/978-3-030-38919-2_48
Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices
Diekert, V., Potapov, I., & Semukhin, P. (2019). Decidability of membership problems for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ and singular matrices. Retrieved from http://arxiv.org/abs/1910.02302v6
Decidability of the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond.
Bell, P. C., Potapov, I., & Semukhin, P. (2019). Decidability of the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond.. In CoRR Vol. abs/1902.10188.
Towards Uniform Online Spherical Tessellations
Bell, P. C., & Potapov, I. (2019). Towards Uniform Online Spherical Tessellations. In F. Manea, B. Martin, D. Paulusma, & G. Primiero (Eds.), Computing with Foresight and Industry Vol. 11558 (pp. 120-131). Durham, UK: Springer. doi:10.1007/978-3-030-22996-2_11
Pushing Lines Helps: Efficient Universal Centralised Transformations for Programmable Matter
Almethen, A., Michail, O., & Potapov, I. (2019). Pushing Lines Helps: Efficient Universal Centralised Transformations for Programmable Matter. doi:10.1007/978-3-030-34405-4_3
Vector Reachability Problem in SL(2,Z)
Semukhin, P., & Potapov, I. (2019). Vector Reachability Problem in SL(2,Z). Journal of Computer and System Sciences, 100, 30-43. doi:10.1016/j.jcss.2018.09.003
On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond
Bell, P. C., Potapov, I., & Semukhin, P. (2019). On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond. Retrieved from http://arxiv.org/abs/1902.10188v3
Polygon Approximations of the Euclidean Circles on the Square Grid by Broadcasting Sequences
Song, H., & Potapov, I. (2019). Polygon Approximations of the Euclidean Circles on the Square Grid by Broadcasting Sequences. In DISCRETE GEOMETRY FOR COMPUTER IMAGERY, DGCI 2019 Vol. 11414 (pp. 444-456). doi:10.1007/978-3-030-14085-4_35
Preface
Filiot, E., Potapov, I., & Jungers, R. (2019). Preface (Vol. 11674 LNCS).
2018
Reachability problems: Special issue
Larsen, K. G., Potapov, I., & Srba, J. (2018). Reachability problems: Special issue. Theoretical Computer Science, 750, 1. doi:10.1016/j.tcs.2018.10.035
De Bruijn graphs and powers of $3/2$
Kurganskyy, O., & Potapov, I. (2018). De Bruijn graphs and powers of $3/2$. Retrieved from http://arxiv.org/abs/1811.02254v2
Vector Ambiguity and Freeness Problems in SL(2, Z)
Ko, S. -K., & Potapov, I. (2018). Vector Ambiguity and Freeness Problems in SL(2, Z). FUNDAMENTA INFORMATICAE, 162(2-3), 161-182. doi:10.3233/FI-2018-1719
Preface
Potapov, I., Spirakis, P., & Worrell, J. (2018). Preface. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 117. doi:10.4230/LIPIcs.MFCS.2018.0
Reachability Problems Problems 2014: Special issue
Ouaknine, J., Potapov, I., & Worrell, J. (2018). Reachability Problems Problems 2014: Special issue. THEORETICAL COMPUTER SCIENCE, 735, 1. doi:10.1016/j.tcs.2018.05.024
On the Identity Problem for the Special Linear Group and the Heisenberg Group
Ko, S. -K., Niskanen, R., & Potapov, I. (2018). On the Identity Problem for the Special Linear Group and the Heisenberg Group. In LIPIcs : Leibniz International Proceedings in Informatics (pp. 1-22). Prague, Czech Republic: Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.ICALP.2018.132
Reachability Problems for One-Dimensional Piecewise Affine Maps
Potapov, I., Bournez, O., & Kurganskyy, O. (2018). Reachability Problems for One-Dimensional Piecewise Affine Maps. International Journal of Foundations of Computer Science, 29(4). doi:10.1142/S0129054118410046
Special Issue Developments in Language Theory (DLT 2015) Preface
Potapov, I., & Semukhin, P. (2018). Special Issue Developments in Language Theory (DLT 2015) Preface. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 29(2), 139-141. doi:10.1142/S0129054118010013
43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK
Potapov, I., Spirakis, P. G., & Worrell, J. (Eds.) (2018). 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK. In MFCS Vol. 117. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
Front Matter, Table of Contents, Preface, Conference Organization.
Potapov, I., Spirakis, P. G., & Worrell, J. (Eds.) (2018). Front Matter, Table of Contents, Preface, Conference Organization.. In MFCS Vol. 117 (pp. 0:i). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from http://www.dagstuhl.de/dagpub/978-3-95977-086-6
Reachability Problems
Potapov, I., & Reynier, P. -A. (Eds.) (2018). Reachability Problems. Springer International Publishing. doi:10.1007/978-3-030-00250-3
Reachability Problems - 12th International Conference, RP 2018, Marseille, France, September 24-26, 2018, Proceedings
Potapov, I., & Reynier, P. -A. (Eds.) (2018). Reachability Problems - 12th International Conference, RP 2018, Marseille, France, September 24-26, 2018, Proceedings. In RP Vol. 11123. Springer.
Reachability Problems in Nondeterministic Polynomial Maps on the Integers
Ko, S. -K., Niskanen, R., & Potapov, I. (2018). Reachability Problems in Nondeterministic Polynomial Maps on the Integers. In DEVELOPMENTS IN LANGUAGE THEORY, DLT 2018 Vol. 11088 (pp. 465-477). doi:10.1007/978-3-319-98654-8_38
Reachability problems: Special issue
Larsen, K. G., Potapov, I., & Srba, J. (2018). Reachability problems: Special issue. THEORETICAL COMPUTER SCIENCE, 750, 1. doi:10.1016/Pcs.2018.10.035
2017
Membership problem in GL(2, Z) extended by singular matrices
Potapov, I., & Semukhin, P. (2017). Membership problem in GL(2, Z) extended by singular matrices. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 83. doi:10.4230/LIPIcs.MFCS.2017.44
Weighted Automata on Infinite Words in the Context of Attacker-Defender Games
Halava, V., Harju, T., Niskanen, R., & Potapov, I. (2017). Weighted Automata on Infinite Words in the Context ofAttacker-Defender Games. Information and Computation, 255(1), 27-44. doi:10.1016/j.ic.2017.05.001
Composition problems for braids: Membership, Identity and Freeness
Ko, S. -K., & Potapov, I. (2017). Composition problems for braids: Membership, Identity and Freeness. Retrieved from http://arxiv.org/abs/1707.08389v1
On the Identity Problem for the Special Linear Group and the Heisenberg Group
Ko, S. -K., Niskanen, R., & Potapov, I. (2017). On the Identity Problem for the Special Linear Group and the Heisenberg Group. Retrieved from http://arxiv.org/abs/1706.04166v5
Vector Ambiguity and Freeness Problems in SL (2, ℤ).
Potapov, I., & Ko, S. (2017). Vector Ambiguity and Freeness Problems in SL (2, ℤ).. In Lecture Notes in Computer Science Vol. 10185 (pp. 373-388). Bern, Switzerland: Springer Verlag. doi:10.1007/978-3-319-55911-7_27
Matrix Semigroup Freeness Problems in SL (2, \mathbb Z).
Potapov, I., & Ko, S. (2017). Matrix Semigroup Freeness Problems in SL (2, \mathbb Z).. In Lecture Notes in Computer Science Vol. 10139 (pp. 268-279). Limerick, Ireland: Springer Verlag. doi:10.1007/978-3-319-51963-0_21
The Identity Problem for Matrix Semigroups in SL2(Z) is NP-complete
Bell, P., Hirvensalo, M., & Potapov, I. (2017). The Identity Problem for Matrix Semigroups in SL2(Z) is NP-complete. In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 187-206). doi:10.1137/1.9781611974782.13
Decidability of the membership problem for 2 × 2 integer matrices
Potapov, I., & Semukhin, P. (2017). Decidability of the membership problem for 2 × 2 integer matrices. In P. N. Klein (Ed.), Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms Vol. 2017 (pp. 170-186). Barcelona, Spain: Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611974782.12
Matrix Semigroup Freeness Problems in SL(2, Z)
Ko, S. -K., & Potapov, I. (2017). Matrix Semigroup Freeness Problems in SL(2, Z). In SOFSEM 2017: THEORY AND PRACTICE OF COMPUTER SCIENCE Vol. 10139 (pp. 268-279). doi:10.1007/978-3-319-51963-0_21
Preface
Potapov, I., & Hague, M. (2017). Preface (Vol. 10506 LNCS).
Reachability Problems - 11th International Workshop, RP 2017, London, UK, September 7-9, 2017, Proceedings
Hague, M., & Potapov, I. (Eds.) (2017). Reachability Problems - 11th International Workshop, RP 2017, London, UK, September 7-9, 2017, Proceedings. In RP Vol. 10506. Springer.
Vector Ambiguity and Freeness Problems in SL (2, ℤ).
Ko, S. -K., & Potapov, I. (2017). Vector Ambiguity and Freeness Problems in SL (2, ℤ).. In T. V. Gopal, G. Jäger, & S. Steila (Eds.), TAMC Vol. 10185 (pp. 373-388). Retrieved from https://doi.org/10.1007/978-3-319-55911-7
2016
Matrix Semigroup Freeness Problems in $\mathrm{SL}(2,\mathbb{Z})$
Ko, S. -K., & Potapov, I. (2016). Matrix Semigroup Freeness Problems in $\mathrm{SL}(2,\mathbb{Z})$. Retrieved from http://arxiv.org/abs/1610.09834v1
Insertion-Deletion Systems over Relational Words.
Potapov, I., Prianychnykova, O., & Verlan, S. (2016). Insertion-Deletion Systems over Relational Words.. In K. G. Larsen, I. Potapov, & J. Srba (Eds.), RP Vol. 9899 (pp. 177-191). Springer. Retrieved from https://doi.org/10.1007/978-3-319-45994-3
Vector Reachability Problem in SL(2,Z)
Potapov, I., & Semukhin, P. (2016). Vector Reachability Problem in SL(2,Z). In Leibniz International Proceedings in Informatics (LIPIcs) Vol. 58. Dagstuhl, Germany: Leibniz International Proceedings in Informatics (LIPIcs). doi:10.4230/LIPIcs.MFCS.2016.84
Undecidability of Two-dimensional Robot Games
Potapov, I., Niskanen, R., & Reichert, J. (2016). Undecidability of Two-dimensional Robot Games. In Leibniz International Proceedings in Informatics Vol. 58 (pp. 73:1-73:13). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.MFCS.2016.73
Undecidability of Two-dimensional Robot Games
Niskanen, R., Potapov, I., & Reichert, J. (2016). Undecidability of Two-dimensional Robot Games. Retrieved from http://arxiv.org/abs/1604.08779v1
Reachability Problems for Infinite State Systems Preface
Abdulla, P. A., Demri, S., Finkel, A., Leroux, J., & Potapov, I. (2016). Reachability Problems for Infinite State Systems Preface. FUNDAMENTA INFORMATICAE, 143(3-4), I-II. doi:10.3233/FI-2016-1311
SOFSEM 2016: Theory and Practice of Computer Science
Freivalds, R. M., Engels, G., & Catania, B. (Eds.) (2016). SOFSEM 2016: Theory and Practice of Computer Science. doi:10.1007/978-3-662-49192-8
Pattern formations with broadcasting automata model.
Potapov, I. (2016). Pattern formations with broadcasting automata model.. In H. Bordihn, R. Freund, B. Nagy, & G. Vaszil (Eds.), NCMA Vol. 321 (pp. 61-73). Österreichische Computer Gesellschaft. Retrieved from http://www.informatik.uni-trier.de/~ley/db/conf/ncma/ncma2016.html
Preface
Larsen, K. G., Potapov, I., & Srba, J. (2016). Preface (Vol. 9899 LNCS).
Reachability Problems - 10th International Workshop, RP 2016, Aalborg, Denmark, September 19-21, 2016, Proceedings
Larsen, K. G., Potapov, I., & Srba, J. (Eds.) (2016). Reachability Problems - 10th International Workshop, RP 2016, Aalborg, Denmark, September 19-21, 2016, Proceedings. In RP Vol. 9899. Springer.
Reachability problems for PAMs
Kurganskyy, O., & Potapov, I. (2016). Reachability Problems for PAMs. In Unknown Conference (pp. 356-368). Springer Berlin Heidelberg. doi:10.1007/978-3-662-49192-8_29
2015
Reachability problems for PAMs
Kurganskyy, O., & Potapov, I. (2015). Reachability problems for PAMs. Retrieved from http://arxiv.org/abs/1510.04121v1
Insertion-Deletion Systems over Relational Words
Potapov, I., Prianychnykova, O., & Verlan, S. (2016). Insertion-Deletion Systems over Relational Words. REACHABILITY PROBLEMS, RP 2016, 9899, 177-191. doi:10.1007/978-3-319-45994-3_13
Vector Reachability Problem in $\mathrm{SL}(2,\mathbb{Z})$
Potapov, I., & Semukhin, P. (2015). Vector Reachability Problem in $\mathrm{SL}(2,\mathbb{Z})$. Retrieved from http://arxiv.org/abs/1510.03227v2
Broadcasting Automata and Patterns on Z<SUP>2</SUP>
Nickson, T., & Potapov, I. (2015). Broadcasting Automata and Patterns on Z<SUP>2</SUP>. In AUTOMATA, UNIVERSALITY, COMPUTATION: TRIBUTE TO MAURICE MARGENSTERN (Vol. 12, pp. 297-340). doi:10.1007/978-3-319-09039-9_14
Developments in Language Theory
Potapov, I. (Ed.) (2015). Developments in Language Theory. In . Springer International Publishing. doi:10.1007/978-3-319-21500-6
On Robot Games of Degree Two
Halava, V., Niskanen, R., & Potapov, I. (2015). On Robot Games of Degree Two. In Unknown Conference (pp. 224-236). Springer International Publishing. doi:10.1007/978-3-319-15579-1_17
Preface
Bojańczyk, M., Lasota, S., & Potapov, I. (2015). Preface (Vol. 9328).
Preface
Potapov, I. (2015). Preface (Vol. 9168).
Reachability Problems
Bojanczyk, M., Lasota, S., & Potapov, I. (Eds.) (2015). Reachability Problems. Springer International Publishing. doi:10.1007/978-3-319-24537-9
2014
Weighted Automata on Infinite Words in the Context of Attacker-Defender Games
Halava, V., Harju, T., Niskanen, R., & Potapov, I. (2015). Weighted Automata on Infinite Words in the Context of Attacker-Defender Games. In EVOLVING COMPUTABILITY Vol. 9136 (pp. 206-215). doi:10.1007/978-3-319-20028-6_21
Broadcasting Automata and Patterns on Z^2
Nickson, T., & Potapov, I. (2014). Broadcasting Automata and Patterns on Z^2. Retrieved from http://arxiv.org/abs/1410.0573v1
Preface
Ouaknine, J., Potapov, I., & Worrell, J. (2014). Preface (Vol. 8762 LNCS).
Reachability Problems
Ouaknine, J., Potapov, I., & Worrell, J. (Eds.) (2014). Reachability Problems. In . Springer International Publishing. doi:10.1007/978-3-319-11439-2
2013
Composition problems for braids
Potapov, I. (2013). Composition problems for braids. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 24 (pp. 175-187). doi:10.4230/LIPIcs.FSTTCS.2013.175
MFCS & CSL 2010 Satellite Workshops: Selected Papers Preface
Ciabattoni, A., Freivalds, R., Kucera, A., Potapov, I., & Szeider, S. (2013). MFCS & CSL 2010 Satellite Workshops: Selected Papers Preface (Vol. 123). doi:10.3233/FI-2013-796
Preface
Delzanno, G., & Potapov, I. (2013). Preface. International Journal of Foundations of Computer Science, 24(2), 161-163. doi:10.1142/S0129054113020024
SPECIAL ISSUE REACHABILITY PROBLEMS (RP 2011) PREFACE
Delzanno, G., & Potapov, I. (2013). SPECIAL ISSUE REACHABILITY PROBLEMS (RP 2011) PREFACE (Vol. 24). doi:10.1142/S0129054113020024
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface
Abdulla, P. A., & Potapov, I. (2013). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface (Vol. 8169 LNCS).
Reachability Problems
Abdulla, P. A., & Potapov, I. (Eds.) (2013). Reachability Problems. In . Springer Berlin Heidelberg. doi:10.1007/978-3-642-41036-9
Reachability Problems, RP 2013
Abdulla, P. A., & Potapov, I. (Eds.) (2013). Reachability Problems, RP 2013 (Vol. 8169). Uppsala: Springer.
2012
Geometric computations by broadcasting automata
Martin, R., Nickson, T., & Potapov, I. (2012). Geometric computations by broadcasting automata. NATURAL COMPUTING, 11(4), 623-635. doi:10.1007/s11047-012-9330-0
Discrete Discs and Broadcasting Sequences
Nickson, T., & Potapov, I. (2012). Discrete Discs and Broadcasting Sequences. In Lecture Notes in Computer Science (pp. 235). Springer Berlin Heidelberg. doi:10.1007/978-3-642-32894-7_23
Reachability Problems
Finkel, A., Leroux, J., & Potapov, I. (Eds.) (2012). Reachability Problems. Springer Berlin Heidelberg. doi:10.1007/978-3-642-33512-9
Mortality for 2 x 2 Matrices Is NP-Hard
Bell, P. C., Hirvensalo, M., & Potapov, I. (2012). Mortality for 2 x 2 Matrices Is NP-Hard. In Unknown Book (Vol. 7464, pp. 148-159). Retrieved from https://www.webofscience.com/
On the Computational Complexity of Matrix Semigroup Problems
Bell, P. C., & Potapov, I. (2012). On the Computational Complexity of Matrix Semigroup Problems. FUNDAMENTA INFORMATICAE, 116(1-4), 1-13. doi:10.3233/FI-2012-663
On algebra of languages representable by vertex-labeled graphs
Grunsky, I., Potapov, I., & Pryanichnikova, E. (2012). On algebra of languages representable by vertex-labeled graphs. THEORETICAL COMPUTER SCIENCE, 426, 42-48. doi:10.1016/j.tcs.2011.08.034
2011
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface
Delzanno, G., & Potapov, I. (2011). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface (Vol. 6945 LNCS).
Geometric Computations by Broadcasting Automata on the Integer Grid
Martin, R., Nickson, T., & Potapov, I. (2011). Geometric Computations by Broadcasting Automata on the Integer Grid. In Unknown Conference (pp. 138-151). Springer Berlin Heidelberg. doi:10.1007/978-3-642-21341-0_18
Planarity of Knots, Register Automata and LogSpace Computability
Lisitsa, A., Potapov, I., & Saleh, R. (2011). Planarity of Knots, Register Automata and LogSpace Computability. In LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS Vol. 6638 (pp. 366-377). Retrieved from https://www.webofscience.com/
SPECIAL ISSUE REACHABILITY PROBELMS (RP 2009) PREFACE
Bournez, O., & Potapov, I. (2011). SPECIAL ISSUE REACHABILITY PROBELMS (RP 2009) PREFACE. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 22(4), 757-760. doi:10.1142/S0129054111008404
Planarity of Knots, Register Automata and LogSpace Computability
Lisitsa, A., Potapov, I., & Saleh, R. (2011). Planarity of Knots, Register Automata and LogSpace Computability. In Unknown Conference (pp. 366-377). Springer Berlin Heidelberg. doi:10.1007/978-3-642-21254-3_29
Reachability Problems - 5th International Workshop, RP 2011, Genoa, Italy, September 28-30, 2011. Proceedings
Delzanno, G., & Potapov, I. (Eds.) (2011). Reachability Problems - 5th International Workshop, RP 2011, Genoa, Italy, September 28-30, 2011. Proceedings. In RP Vol. 6945. Springer.
Reachability Problems, RP2011
Delzanno, G., & Potapov, I. (Eds.) (2011). Reachability Problems, RP2011 (Vol. 6945). Berlin: Springer.
Special Issue - Reachability Problems (RP 2009)
Bournez, O., & Potapov, I. (Eds.) (2011). Special Issue - Reachability Problems (RP 2009) (Vol. 22). Singapore: World Scientific. Retrieved from http://www.worldscinet.com/ijfcs/22/2204/S01290541112204.html
2010
ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS
Bell, P. C., & Potapov, I. (2010). ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 21(6), 963-978. doi:10.1142/S0129054110007660
A measure of state transition of collective of stateless automata in discrete environment
Kurganskyy, O., & Potapov, I. (2010). A measure of state transition of collective of stateless automata in discrete environment. Retrieved from http://arxiv.org/abs/1007.2353v1
On decision problems for parameterized machines
Ibarra, O. H., Potapov, I., & Yen, H. -C. (2010). On decision problems for parameterized machines. THEORETICAL COMPUTER SCIENCE, 411(7-9), 1192-1201. doi:10.1016/j.tcs.2009.12.013
Reachability Problems
Kučera, A., & Potapov, I. (Eds.) (2010). Reachability Problems. Springer Berlin Heidelberg. doi:10.1007/978-3-642-15349-5
2009
The Identity Correspondence Problem and Its Applications
Bell, P. C., & Potapov, I. (2009). The Identity Correspondence Problem and Its Applications. In ALGORITHMS AND COMPUTATION, PROCEEDINGS Vol. 5878 (pp. 657-667). Retrieved from https://www.webofscience.com/
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface
Bournez, O., & Potapov, I. (2009). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface (Vol. 5797 LNCS).
SPECIAL ISSUE REACHABILITY PROBLEMS (RP 2008) PREFACE
Halava, V., & Potapov, I. (2009). SPECIAL ISSUE REACHABILITY PROBLEMS (RP 2008) PREFACE. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 20(5), 775-777. doi:10.1142/S0129054109006875
On the Computational Power of Querying the History
Lisitsa, A., & Potapov, I. (2009). On the Computational Power of Querying the History. FUNDAMENTA INFORMATICAE, 91(2), 395-409. doi:10.3233/FI-2009-0049
On Descriptional Complexity of the Planarity Problem for Gauss Words
Kurlin, V., Lisitsa, A., Potapov, I., & Saleh, R. (2009). On Descriptional Complexity of the Planarity Problem for Gauss Words. Retrieved from http://arxiv.org/abs/0907.4180v1
Automata on Gauss Words
Lisitsa, A., Potapov, I., & Saleh, R. (2009). Automata on Gauss Words. In LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS Vol. 5457 (pp. 505-517). doi:10.1007/978-3-642-00982-2_43
The Identity Correspondence Problem and its Applications
Bell, P. C., & Potapov, I. (2009). The Identity Correspondence Problem and its Applications. World Scientific, 21, 6. Retrieved from http://dx.doi.org/10.1142/10.1142/S0129054110007660
Reachability Problems
Bournez, O., & Potapov, I. (Eds.) (2009). Reachability Problems (Vol. 5797). Berlin: Springer. Retrieved from http://www.springer.com/computer/mathematics/book/978-3-642-04419-9
Reachability Problems, 3rd International Workshop, RP 2009, Palaiseau, France, September 23-25, 2009. Proceedings
Bournez, O., & Potapov, I. (Eds.) (2009). Reachability Problems, 3rd International Workshop, RP 2009, Palaiseau, France, September 23-25, 2009. Proceedings. In RP Vol. 5797. Springer.
Special Issue of International Journal of Foundations of Computer Science
Halava, V., & Potapov, I. (Eds.) (2009). Special Issue of International Journal of Foundations of Computer Science (Vol. 20(5)). -: World Scientific.
2008
Preface
Halava, V., & Potapov, I. (2008). Preface. Electronic Notes in Theoretical Computer Science, 223, 1-2. doi:10.1016/j.entcs.2008.12.026
MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
BELL, P., HALAVA, V., HARJU, T., KARHUMÄKI, J., & POTAPOV, I. (2008). MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM. International Journal of Algebra and Computation, 18(08), 1231-1241. doi:10.1142/s0218196708004925
Reachability problems in quaternion matrix and rotation semigroups
Bell, P., & Potapov, I. (2008). Reachability problems in quaternion matrix and rotation semigroups. INFORMATION AND COMPUTATION, 206(11), 1353-1361. doi:10.1016/j.ic.2008.06.004
International Journal of Foundations of Computer Science: Preface
Halava, V., & Potapov, I. (2008). International Journal of Foundations of Computer Science: Preface. International Journal of Foundations of Computer Science, 19(4), 915-917. doi:10.1142/S0129054108006030
Reachability probelms (RP 2007) - Preface
Halava, V., & Potapov, I. (2008). Reachability probelms (RP 2007) - Preface. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 19(4), 915-917. doi:10.1142/S0129054108006030
Reachability problems in low-dimensional iterative maps
Kurganskyy, O., Potapov, I., & Sancho-Caparrini, F. (2008). Reachability problems in low-dimensional iterative maps. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 19(4), 935-951. doi:10.1142/S0129054108006054
On undecidability bounds for matrix decision problems
Bell, P., & Potapov, I. (2008). On undecidability bounds for matrix decision problems. THEORETICAL COMPUTER SCIENCE, 391(1-2), 3-13. doi:10.1016/j.tcs.2007.10.025
Discrete analogues of dynamical systems and their applications for secure data transmission
Kozlovskyy, V., Kurganskyy, O., Lisitsa, A., Potapov, I., & Sapunov, S. (2008). Discrete analogues of dynamical systems and their applications for secure data transmission. Liverpool: NATO, The Science for Peace and Security (SPS).
MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
Bell, P., Halava, V., Harju, T., Karhumaki, J., & Potapov, I. (2008). MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM. INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 18(8), 1231-1241. doi:10.1142/S0218196708004925
Periodic and infinite traces in matrix semigroups
Bell, P., & Potapov, I. (2008). Periodic and infinite traces in matrix semigroups. In SOFSEM 2008: THEORY AND PRACTICE OF COMPUTER SCIENCE Vol. 4910 (pp. 148-+). Retrieved from https://www.webofscience.com/
Preface. Proceedings of the Second Workshop on Reachability Problems in Computational Models (RP 2008)
Halava, V., & Potapov, I. (2008). Preface. Proceedings of the Second Workshop on Reachability Problems in Computational Models (RP 2008). Electronic Notes in Theoretical Computer Science, 223, 1-2. Retrieved from doi:10.1016/j.entcs.2008.12.026
Proceedings of the 2nd Workshop on Reachability Problems
Halava, V., & Potapov, I. (Eds.) (2008). Proceedings of the 2nd Workshop on Reachability Problems. In Workshop on Reachability Problems, RP2008 (pp. 300). Amsterdam: ENTCS, Elsevier. Retrieved from http://www.sciencedirect.com/science/journal/15710661
Walking Automata on a Class of Geometric Environments
Kurganskyy, O., & Potapov, I. (2008). Walking Automata on a Class of Geometric Environments. Proceedings of the Institute of Applied Mathematics and Mechanics, NAS of Ukraine, v.17, 96-108.
2007
Time efficient centralized gossiping in radio networks
Gasieniec, L., Potapov, I., & Xin, Q. (2007). Time efficient centralized gossiping in radio networks. THEORETICAL COMPUTER SCIENCE, 383(1), 45-58. doi:10.1016/j.tcs.2007.03.059
On the membership of invertible diagonal and scalar matrices
Bell, P., & Potapov, I. (2007). On the membership of invertible diagonal and scalar matrices. THEORETICAL COMPUTER SCIENCE, 372(1), 37-45. doi:10.1016/j.tcs.2006.11.011
Computation in one-dimensional piecewise maps
Kurganskyy, O., Potapov, I., & Caparrini, F. S. (2007). Computation in one-dimensional piecewise maps. In Hybrid Systems: Computation and Control, Proceedings Vol. 4416 (pp. 706-709). Retrieved from https://www.webofscience.com/
Deterministic communication in radio networks with large labels
Gasieniec, L., Pagourtzis, A., Potapov, I., & Radzik, T. (2007). Deterministic communication in radio networks with large labels. ALGORITHMICA, 47(1), 97-117. doi:10.1007/s00453-006-1212-3
Matrix equations and Hilbert's tenth problem
Bell, P., Halava, V., Harju, T., Karhumäki, J., & Potapov, I. (2007). Matrix equations and Hilbert's tenth problem. TUCS Technical report, (840), 1-16. Retrieved from http://www.tucs.fi/
Proceedings of the Satellite Workshops of DLT 2007
Hirvensalo, M., Halava, V., Potapov, I., & Kari, J. (Eds.) (2007). Proceedings of the Satellite Workshops of DLT 2007. In Workshop on Reachability Problems Vol. 45 (pp. 255). Turku: Turku Centre for Computer Science. Retrieved from http://www.tucs.fi/publications/insight.php?id=pHiHaPoKa07a&table=proceeding
Reachability problems in low-dimensional iterative maps
Kurganskyy, O., Potapov, I., & Sancho-Caparrini, F. (2007). Reachability problems in low-dimensional iterative maps. In Workshop on Reachability Problems Vol. 45 (pp. 38-52). Turku: TUCS General Publications.
Reachability problems in quaternion matrix and rotation semigroups
Bell, P., & Potapov, I. (2007). Reachability problems in quaternion matrix and rotation semigroups. In MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2007, PROCEEDINGS Vol. 4708 (pp. 346-+). Retrieved from https://www.webofscience.com/
2006
In time alone: On the computational power of querying the history
Lisitsa, A., & Potapov, I. (2006). In time alone: On the computational power of querying the history. In TIME 2006: THIRTEENTH INTERNATIONAL SYMPOSIUM ON TEMPORAL REPRESENTATION AND REASONING, PROCEEDINGS (pp. 42-+). Retrieved from https://www.webofscience.com/
Lowering undecidability bounds for decision questions in matrices
Bell, P., & Potapov, I. (2006). Lowering undecidability bounds for decision questions in matrices. In DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS Vol. 4036 (pp. 375-385). Retrieved from https://www.webofscience.com/
On a maximal NFA without mergible states
Grunsky, I., Kurganskyy, O., & Potapov, I. (2006). On a maximal NFA without mergible states. In COMPUTER SCIENCE - THEORY AND APPLICATIONS Vol. 3967 (pp. 202-210). Retrieved from https://www.webofscience.com/
2005
Real-time traversal in grammar-based compressed files
Gasieniec, L., Kolpakov, R., Potapov, I., & Sant, P. (2005). Real-time traversal in grammar-based compressed files. In DCC 2005: Data Compression Conference, Proceedings (pp. 458). Retrieved from https://www.webofscience.com/
Space efficient search for maximal repetitions
Gasieniec, L., Kolpakov, R., & Potapov, I. (2005). Space efficient search for maximal repetitions. THEORETICAL COMPUTER SCIENCE, 339(1), 35-48. doi:10.1016/j.tcs.2005.01.006
Computation in one-dimensional piecewise maps and planar pseudo-billiard systems
Kurganskyy, O., & Potapov, I. (2005). Computation in one-dimensional piecewise maps and planar pseudo-billiard systems. In UNCONVENTIONAL COMPUTATION, PROCEEDINGS Vol. 3699 (pp. 169-175). Retrieved from https://www.webofscience.com/
Languages representable by vertex-labeled graphs
Grunsky, I., Kurganskyy, O., & Potapov, I. (2005). Languages representable by vertex-labeled graphs. In MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2005, PROCEEDINGS Vol. 3618 (pp. 435-446). Retrieved from https://www.webofscience.com/
On temporal logic between between propositional and first-order
Lisitsa, A., Potapov, I., & et al. (2005). On temporal logic between between propositional and first-order. In S. S. Goncharov (Ed.), The 9th Asian Logic Conference (pp. 101-102). Novosibirsk: Novosibirsk State University. Retrieved from http://www.ict.nsc.ru/ws/ALC-9/index.en.html
On the membership of invertible diagonal matrices
Bell, P., & Potapov, I. (2005). On the membership of invertible diagonal matrices. In DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS Vol. 3572 (pp. 146-157). Retrieved from https://www.webofscience.com/
Universality of Walking Automata on a Class of Geometric Environments
Kurganskyy, O., & Potapov, I. (2005). Universality of Walking Automata on a Class of Geometric Environments. In B. Cooper, B. Löwe, & L. Torenvliet (Eds.), Computability in Europe: New Computational Paradigms Vol. X-2005 (pp. 122-131). Amsterdam: The Institute for Logic, Language and Computation. Retrieved from http://www.illc.uva.nl/Publications/ResearchReports/X-2005-01.text.pdf
2004
Temporal logic with predicate λ-abstraction.
Lisitsa, A., & Potapov, I. (2005). Temporal logic with predicate λ-abstraction.. In 12TH INTERNATIONAL SYMPOSIUM ON TEMPORAL REPRESENTATION AND REASONING, PROCEEDINGS (pp. 147-155). doi:10.1109/TIME.2005.34
From post systems to the reachability problems for matrix semigroups and multicounter automata
Potapov, I. (2004). From post systems to the reachability problems for matrix semigroups and multicounter automata. In DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS Vol. 3340 (pp. 345-356). Retrieved from https://www.webofscience.com/
Mathematical Foundations of Computer Science 2004
Fiala, J., Koubek, V., & Kratochvíl, J. (Eds.) (2004). Mathematical Foundations of Computer Science 2004. In . Springer Berlin Heidelberg. doi:10.1007/b99679
Membership and reachability problems for row-monomial transformations
Lisitsa, A., & Potapov, I. (2004). Membership and reachability problems for row-monomial transformations. In MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004, PROCEEDINGS Vol. 3153 (pp. 623-634). Retrieved from https://www.webofscience.com/
On the computation power of finite automata in two-dimensional environments
Kurganskyy, O., & Potapov, I. (2004). On the computation power of finite automata in two-dimensional environments. DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS, 3340, 261-271. Retrieved from https://www.webofscience.com/
Temporal logic with predicate abstraction
Lisitsa, A., & Potapov, I. (2004). Temporal logic with predicate abstraction. CoRR, cs.LO/0410072.
Time Efficient Gossiping in Known Radio Networks
Gąsieniec, L., Potapov, I., & Xin, Q. (2004). Time Efficient Gossiping in Known Radio Networks. In Unknown Conference (pp. 173-184). Springer Berlin Heidelberg. doi:10.1007/978-3-540-27796-5_16
Time efficient gossiping in known radio networks
Gasieniec, L., Potapov, I., & Xin, Q. (2004). Time efficient gossiping in known radio networks. In STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, PROCEEDING Vol. 3104 (pp. 173-184). Retrieved from https://www.webofscience.com/
2003
Time/space efficient compressed pattern matching
Gasieniec, L., & Potapov, I. (2003). Time/space efficient compressed pattern matching. FUNDAMENTA INFORMATICAE, 56(1-2), 137-154. Retrieved from https://www.webofscience.com/
Coarse-grained parallel transitive closure algorithm: Path decomposition technique
Gibbons, A., Pagourtzis, A., Potapov, I., & Rytter, W. (2003). Coarse-grained parallel transitive closure algorithm: Path decomposition technique. COMPUTER JOURNAL, 46(4), 391-400. doi:10.1093/comjnl/46.4.391
Space efficient search for maximal repetitions
Gasieniec, L., Kolpakov, R., & Potapov, I. (2003). Space efficient search for maximal repetitions. In 4th International Conference on Words, WORDS'2003. Turku: Turku University.
2002
Deterministic communication in radio networks with large labels
Gasieniec, L., Pagourtzis, A., & Potapov, I. (2002). Deterministic communication in radio networks with large labels. In ALGORITHMS-ESA 2002, PROCEEDINGS Vol. 2461 (pp. 512-524). Retrieved from https://www.webofscience.com/
Gossiping with unit messages in known radio networks
Gasieniec, L., & Potapov, I. (2002). Gossiping with unit messages in known radio networks. In FOUNDATIONS OF INFORMATION TECHNOLOGY IN THE ERA OF NETWORK AND MOBILE COMPUTING Vol. 96 (pp. 193-205). Retrieved from https://www.webofscience.com/
Observations on parallel computation of transitive and Max-Closure problems
Pagourtzis, A., Potapov, I., & Rytter, W. (2002). Observations on parallel computation of transitive and Max-Closure problems. In RECENT ADVANCES IN PARALLEL VIRTUAL MACHINE AND MESSAGE PASSING INTERFACE, PROCEEDINGS Vol. 2474 (pp. 217-225). Retrieved from https://www.webofscience.com/
2001
PVM Computation of the Transitive Closure: The Dependency Graph Approach
Pagourtzis, A., Potapov, I., & Rytter, W. (2001). PVM Computation of the Transitive Closure: The Dependency Graph Approach. In Unknown Conference (pp. 249-256). Springer Berlin Heidelberg. doi:10.1007/3-540-45417-9_35
Time/Space Efficient Compressed Pattern Matching
Gasieniec, L., & Potapov, I. (2001). Time/Space Efficient Compressed Pattern Matching. In Unknown Conference (pp. 138-149). Springer Berlin Heidelberg. doi:10.1007/3-540-44669-9_15
1999
On the bound of algorithmic resolvability of correctness problems of automaton interaction through communication channels
Kurganskii, A. N., & Potapov, I. G. (1999). On the bound of algorithmic resolvability of correctness problems of automaton interaction through communication channels. Cybernetics and Systems Analysis, 35(3), 385-391. doi:10.1007/bf02733427