• 116 Citations
  • 6 h-Index
20122019
If you made any changes in Pure these will be visible here soon.

Research Output 2012 2019

2019

Comparison of LZ77-type parsings

Kosolobov, D. & Shur, A. M., 1 Jan 2019, In : Information Processing Letters. 141, p. 25-29 5 p.

Research output: Contribution to journalArticleResearchpeer-review

Parsing
Overlap
Encoding
Strings
Denote

Searching long repeats in streams

Shur, A. M. & Merkurev, O., 1 Jun 2019, 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019. Pisanti, N. & Pissis, S. P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 31. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 128).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Data storage equipment
2018
3 Citations (Scopus)

EERTREE: An efficient data structure for processing palindromes in strings

Rubinchik, M. & Shur, A. M., 1 Feb 2018, In : European Journal of Combinatorics. 68, p. 249-265 17 p.

Research output: Contribution to journalArticleResearchpeer-review

Palindrome
Data Structures
Strings
Suffix Tree
Suffix

Square-Free Partial Words with Many Wildcards

Gasnikov, D. & Shur, A. M., 1 Aug 2018, In : International Journal of Foundations of Computer Science. 29, 5, p. 845-860 16 p.

Research output: Contribution to journalArticleResearchpeer-review

String periods in the order-preserving model

Gourdel, G., Kociumaka, T., Radoszewski, J., Rytter, W., Shur, A. & Walen, T., 2 Feb 2018, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 96. 38

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2017
2 Citations (Scopus)

Counting palindromes in substrings

Rubinchik, M. & Shur, A. M., 2017, String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings. Springer Verlag, Vol. 10508 LNCS. p. 290-303 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10508 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Palindrome
Counting
Strings
Data structures
Query

Lower bounds on words separation: Are there short identities in transformation semigroups?

Bulatov, A., Karpova, O., Shur, A. M. & Startsev, K., 25 Aug 2017, In : Electronic Journal of Combinatorics. 24, 3, P3.35.

Research output: Contribution to journalArticleResearchpeer-review

Transformation Semigroups
Finite automata
Inverse problems
Lower bound
Unary
3 Citations (Scopus)

On the size of Lempel-Ziv and Lyndon factorizations

Kärkkäinen, J., Kempa, D., Nakashima, Y., Puglisi, S. J. & Shur, A. M., 1 Mar 2017, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 66. 45

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Factorization

On the tree of binary cube-free words

Petrova, E. A. & Shur, A. M., 2017, Developments in Language Theory - 21st International Conference, DLT 2017, Proceedings. Springer Verlag, Vol. 10396 LNCS. p. 296-307 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10396 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Regular hexahedron
Binary
Path
Prefix
Branching
5 Citations (Scopus)

Palindromic length in linear time

Borozdin, K., Kosolobov, D., Rubinchik, M. & Shur, A. M., 1 Jul 2017, 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 78. 23

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2016
13 Citations (Scopus)

EERTREE: An efficient data structure for processing palindromes in strings

Rubinchik, M. & Shur, A. M., 2016, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag, Vol. 9538. p. 321-333 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9538).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Palindrome
Data structures
Data Structures
Strings
Suffix Tree
5 Citations (Scopus)

More on quantum, stochastic, and pseudo stochastic languages with few states

Shur, A. M. & Yakaryılmaz, A., 1 Mar 2016, In : Natural Computing. 15, 1, p. 129-141 13 p.

Research output: Contribution to journalArticleResearchpeer-review

Finite automata
5 Citations (Scopus)

Palindromic rich words and run-length encodings

Guo, C., Shallit, J. & Shur, A. M., 1 Dec 2016, In : Information Processing Letters. 116, 12, p. 735-738 4 p.

Research output: Contribution to journalArticleResearchpeer-review

Run-length Encoding
Growth Function
Integer Partitions
Lower bound
Sufficient Conditions

Special Issue Developments in Language Theory (DLT 2014) Preface

Shur, A., Feb 2016, In : International Journal of Foundations of Computer Science. 27, 2, p. 101-102 2 p.

Research output: Contribution to journalEditorialResearchpeer-review

2 Citations (Scopus)

Ternary square-free partial words with many wildcards

Gasnikov, D. & Shur, A. M., 2016, Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings. Springer Verlag, Vol. 9840. p. 177-189 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9840).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Partial Words
Square free
Ternary
Flexibility
6 Citations (Scopus)

The Number of Distinct Subpalindromes in Random Words

Rubinchik, M. & Shur, A. M., 2016, In : Fundamenta Informaticae. 145, 3, p. 371-384 14 p.

Research output: Contribution to journalArticleResearchpeer-review

Distinct
Palindrome
Asymmetry
Odd
Experimental Data
3 Citations (Scopus)

Tight tradeoffs for real-time approximation of longest palindromes in streams

Gawrychowski, P., Merkurev, O., Shur, A. M. & Uznański, P., 1 Jun 2016, 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 54. p. 18.1-18.13

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Approximation algorithms
Data storage equipment
Processing
2015
1 Citation (Scopus)

Generating square-free words efficiently

Shur, A. M., 1 Jan 2015, In : Theoretical Computer Science. 601, p. 67-72 6 p.

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

On the Tree of Ternary Square-Free Words

Petrova, E. A. & Shur, A. M., 2015, COMBINATORICS ON WORDS, WORDS 2015. Manea, F. & Nowotka, D. (eds.). Springer Verlag, Vol. 9304. p. 223-236 14 p. (Lecture Notes in Computer Science; vol. 9304).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Square free
Ternary
Path
Prefix
Set of points
1 Citation (Scopus)

Optimal Bounds for the Similarity Density of the Thue-Morse Word with Overlap-Free and 7/3 -Power-Free Infinite Binary Words

Du, C. F., Shallit, J. & Shur, A. M., 1 Dec 2015, In : International Journal of Foundations of Computer Science. 26, 8, p. 1147-1165 19 p.

Research output: Contribution to journalArticleResearchpeer-review

13 Citations (Scopus)

Pal(k) is Linear Recognizable Online

Kosolobov, D., Rubinchik, M. & Shur, A. M., 2015, SOFSEM 2015: THEORY AND PRACTICE OF COMPUTER SCIENCE. Italiano, GF., MargariaSteffen, T., Pokorny, J., Quisquater, JJ. & Wattenhofer, R. (eds.). Springer Verlag, Vol. 8939. p. 289-301 13 p. (Lecture Notes in Computer Science; vol. 8939).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)

Searching for Zimin patterns

Rytter, W. & Shur, A. M., 16 Mar 2015, In : Theoretical Computer Science. 571, C, p. 50-57 8 p.

Research output: Contribution to journalArticleResearchpeer-review

2014
3 Citations (Scopus)

Binary patterns in binary cube-free words: Avoidability and growth

Mercas, R., Ochem, P., Samsonov, A. V. & Shur, A. M., Oct 2014, In : RAIRO - Theoretical Informatics and Applications. 48, 4, p. 369-389 21 p.

Research output: Contribution to journalArticleResearchpeer-review

Growth of Power-Free Languages over Large Alphabets

Shur, A. M., Feb 2014, In : Theory of Computing Systems. 54, 2, p. 224-243 20 p.

Research output: Contribution to journalArticleResearchpeer-review

Languages with a finite antidictionary: Some growth questions

Shur, A. M., Dec 2014, In : International Journal of Foundations of Computer Science. 25, 8, p. 937-953 17 p.

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Periodic Partial Words and Random Bipartite Graphs

Idiatulina, L. A. & Shur, A. M., 2014, In : Fundamenta Informaticae. 132, 1, p. 15-31 17 p.

Research output: Contribution to journalArticleResearchpeer-review

Partial Words
Random Graphs
Bipartite Graph
Connectedness
Interaction
3 Citations (Scopus)

Quantum, stochastic, and pseudo stochastic languages with few states

Shur, A. M. & YakaryIlmaz, A., 1 Jan 2014, In : Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8553 LNCS, p. 327-339 13 p.

Research output: Contribution to journalArticleResearchpeer-review

Finite Automata
Finite automata
Unary
Probabilistic Automata
Language
2013
8 Citations (Scopus)

Finding distinct subpalindromes online

Kosolobov, D., Rubinchik, M. & Shur, A. M., 2013, Proceedings of the Prague Stringology Conference 2013, PSC 2013. p. 63-69 7 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Palindrome
Distinct
Unordered
Online Algorithms
Optimality

Languages with a finite antidictionary: Growth-preserving transformations and available orders of growth

Shur, A. M., 2013, Developments in Language Theory - 17th International Conference, DLT 2013, Proceedings. Vol. 7907 LNCS. p. 445-457 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7907 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Order of Growth
Automata
Formal languages
Structural properties
Condensation

Preface

Bulatov, A. & Shur, A., 2013, In : Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7913 LNCS

Research output: Contribution to journalArticleResearchpeer-review

2012
2 Citations (Scopus)

CONSTRUCTING PREMAXIMAL BINARY CUBE-FREE WORDS OF ANY LEVEL

Petrova, E. A. & Shur, A. M., Dec 2012, In : International Journal of Foundations of Computer Science. 23, 8, p. 1595-1609 15 p.

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)

Constructing premaximal ternary square-free words of any level

Petrova, E. A. & Shur, A. M., 2012, Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Proceedings. Vol. 7464 LNCS. p. 752-763 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7464 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Square free
Ternary
Extendability
Open Problems
Resolve
4 Citations (Scopus)

Deciding context equivalence of binary overlap-free words in linear time

Shur, A. M., Jun 2012, In : Semigroup Forum. 84, 3, p. 447-471 25 p.

Research output: Contribution to journalArticleResearchpeer-review

Word problem
Linear Time
Overlap
Equivalence
Binary
11 Citations (Scopus)

Growth properties of power-free languages

Shur, A. M., Nov 2012, In : Computer Science Review. 6, 5-6, p. 187-208 22 p.

Research output: Contribution to journalReview articleResearchpeer-review

Formal languages
Growth Function
Line
Symbolic Dynamics
Formal Languages
7 Citations (Scopus)

On Abelian repetition threshold

Samsonov, A. V. & Shur, A. M., Jan 2012, In : RAIRO - Theoretical Informatics and Applications. 46, 1, p. 147-163 17 p.

Research output: Contribution to journalArticleResearchpeer-review

Fractional Powers
Lower bound
Exponential Growth
Upper bound
Analogue

ON PANSIOT WORDS AVOIDING 3-REPETITIONS

Gorbunova, I. A. & Shur, A. M., Dec 2012, In : International Journal of Foundations of Computer Science. 23, 8, p. 1583-1594 12 p.

Research output: Contribution to journalArticleResearchpeer-review

Formal languages
3 Citations (Scopus)

On two stronger versions of Dejean's conjecture

Tunev, I. N. & Shur, A. M., 2012, Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Proceedings. Vol. 7464 LNCS. p. 800-812 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7464 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Odd
Repetition