{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:53:04Z","timestamp":1764557584910,"version":"build-2065373602"},"reference-count":90,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,1,5]],"date-time":"2021-01-05T00:00:00Z","timestamp":1609804800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Text indexing is a classical algorithmic problem that has been studied for over four decades: given a text T, pre-process it off-line so that, later, we can quickly count and locate the occurrences of any string (the query pattern) in T in time proportional to the query\u2019s length. The earliest optimal-time solution to the problem, the suffix tree, dates back to 1973 and requires up to two orders of magnitude more space than the plain text just to be stored. In the year 2000, two breakthrough works showed that efficient queries can be achieved without this space overhead: a fast index be stored in a space proportional to the text\u2019s entropy. These contributions had an enormous impact in bioinformatics: today, virtually any DNA aligner employs compressed indexes. Recent trends considered more powerful compression schemes (dictionary compressors) and generalizations of the problem to labeled graphs: after all, texts can be viewed as labeled directed paths. In turn, since finite state automata can be considered as a particular case of labeled graphs, these findings created a bridge between the fields of compressed indexing and regular language theory, ultimately allowing to index regular languages and promising to shed new light on problems, such as regular expression matching. This survey is a gentle introduction to the main landmarks of the fascinating journey that took us from suffix trees to today\u2019s compressed indexes for labeled graphs and regular languages.<\/jats:p>","DOI":"10.3390\/a14010014","type":"journal-article","created":{"date-parts":[[2021,1,5]],"date-time":"2021-01-05T21:18:57Z","timestamp":1609881537000},"page":"14","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Subpath Queries on Compressed Graphs: A Survey"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3553-4953","authenticated-orcid":false,"given":"Nicola","family":"Prezza","sequence":"first","affiliation":[{"name":"Department of Environmental Sciences, Informatics and Statistics, Ca\u2019 Foscari University, Dorsoduro, 3246, 30123 Venice, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2021,1,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","article-title":"Efficient randomized pattern-matching algorithms","volume":"31","author":"Karp","year":"1987","journal-title":"IBM J. Res. Dev."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1145\/359146.359148","article-title":"On improving the worst case running time of the Boyer-Moore string matching algorithm","volume":"22","author":"Galil","year":"1979","journal-title":"Commun. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1137\/0215007","article-title":"The Boyer-Moore-Galil string searching strategies revisited","volume":"15","author":"Apostolico","year":"1986","journal-title":"SIAM J. Comput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","article-title":"Fast Pattern Matching in Strings","volume":"6","author":"Knuth","year":"1977","journal-title":"SIAM J. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Navarro, G. (2016). Compact Data Structures\u2014A Practical Approach, Cambridge University Press.","DOI":"10.1017\/CBO9781316588284"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., Belazzougui, D., Cunial, F., and Tomescu, A.I. (2015). Genome-Scale Algorithm Design, Cambridge University Press.","DOI":"10.1017\/CBO9781139940023"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1216370.1216372","article-title":"Compressed Full-Text Indexes","volume":"39","author":"Navarro","year":"2007","journal-title":"ACM Comput. Surv."},{"key":"ref_8","unstructured":"Navarro, G. (2020, November 10). Indexing Highly Repetitive String Collections, Part I: Repetitiveness Measures. Available online: https:\/\/arxiv.org\/abs\/2004.02781."},{"key":"ref_9","unstructured":"Navarro, G. (2020, November 10). Indexing Highly Repetitive String Collections, Part II: Compressed Indexes. Available online: https:\/\/link.springer.com\/chapter\/10.1007\/978-3-642-35926-2_29."},{"key":"ref_10","unstructured":"The Computational Pan-Genomics Consortium (2016). Computational pan-genomics: Status, promises and challenges. Briefings Bioinform., 19, 118\u2013135."},{"key":"ref_11","unstructured":"Manber, U., and Myers, G. (1990, January 22\u201324). Suffix arrays: A new method for on-line string searches. Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Baeza-Yates, R.A., and Gonnet, G.H. (1989, January 25\u201328). A New Approach to Text Searching. Proceedings of the 12th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR\u201989), Cambridge, MA, USA.","DOI":"10.1145\/75334.75352"},{"key":"ref_13","first-page":"82","article-title":"New Indices for Text: Pat Trees and Pat Arrays","volume":"66","author":"Gonnet","year":"1992","journal-title":"Inf. Retr. Data Struct. Algorithms"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Weiner, P. (1973, January 15\u201317). Linear pattern matching algorithms. Proceedings of the 14th Annual Symposium on Switching and Automata Theory (swat 1973), Iowa City, IA, USA.","DOI":"10.1109\/SWAT.1973.13"},{"key":"ref_15","unstructured":"K\u00e4rkk\u00e4inen, J., and Ukkonen, E. (1996, January 8\u20139). Lempel-Ziv parsing and sublinear-size index structures for string matching. Proceedings of the 3rd South American Workshop on String Processing (WSP\u201996), Recife, Brazil."},{"key":"ref_16","unstructured":"Ferragina, P., and Manzini, G. (2000, January 12\u201314). Opportunistic data structures with applications. Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Grossi, R., and Vitter, J.S. (2000, January 21\u201323). Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching (Extended Abstract). Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC\u201900), Portland, OR, USA.","DOI":"10.1145\/335305.335351"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","article-title":"Efficient Storage and Retrieval by Content and Address of Static Files","volume":"21","author":"Elias","year":"1974","journal-title":"J. ACM"},{"key":"ref_19","unstructured":"Fano, R.M. (1971). On the Number of Bits Required to Implement an Associative Memory, Massachusetts Institute of Technology. Project MAC."},{"key":"ref_20","unstructured":"Burrows, M., and Wheeler, D.J. (2020, November 10). A Block-Sorting Lossless Data Compression Algorithm. Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.3.8069."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows\u2014Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2012.02.006","article-title":"On Compressing and Indexing Repetitive Sequences","volume":"483","author":"Kreft","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Gagie, T., Navarro, G., and Prezza, N. (2020). Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space. J. ACM, 67.","DOI":"10.1145\/3375890"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., and Navarro, G. (2005, January 19\u201322). Succinct suffix arrays based on run-length encoding. Proceedings of the Annual Symposium on Combinatorial Pattern Matching, Jeju Island, Korea.","DOI":"10.1007\/11496656_5"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Sir\u00e9n, J., V\u00e4lim\u00e4ki, N., M\u00e4kinen, V., and Navarro, G. (2008, January 10\u201312). Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections. Proceedings of the 15th International Symposium on String Processing and Information Retrieval (SPIRE), Melbourne, Australia.","DOI":"10.1007\/978-3-540-89097-3_17"},{"key":"ref_27","unstructured":"Claude, F., and Navarro, G. (2012, January 21\u201325). Improved Grammar-Based Compressed Indexes. Proceedings of the 19th International Symposium on String Processing and Information Retrieval (SPIRE), Cartagena de Indias, Colombia."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.tcs.2018.09.007","article-title":"Universal compressed text indexing","volume":"762","author":"Navarro","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Kempa, D., and Prezza, N. (2018, January 25\u201329). At the Roots of Dictionary Compression: String Attractors. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), Los Angeles, CA, USA.","DOI":"10.1145\/3188745.3188814"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Navarro, G., and Prezza, N. (2020, January 25\u201319). Towards a Definitive Measure of Repetitiveness. Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN), Sao Paulo, Brazil. to appear.","DOI":"10.1007\/978-3-030-61792-9_17"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Gagie, T., Navarro, G., and Prezza, N. (2018, January 14\u201319). On the approximation ratio of Lempel-Ziv parsing. Proceedings of the Latin American Symposium on Theoretical Informatics, Buenos Aires, Argentina.","DOI":"10.1007\/978-3-319-77404-6_36"},{"key":"ref_32","first-page":"1","article-title":"Optimal-Time Dictionary-Compressed Indexes","volume":"31","author":"Christiansen","year":"2020","journal-title":"ACM Trans. Algorithms"},{"key":"ref_33","unstructured":"Maneth, S., and Peternek, F. (2015). A Survey on Methods and Systems for Graph Compression. arXiv."},{"key":"ref_34","unstructured":"Besta, M., and Hoefler, T. (2019). Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. arXiv."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1613676.1613680","article-title":"Compressing and Indexing Labeled Trees, with Applications","volume":"57","author":"Ferragina","year":"2009","journal-title":"J. ACM"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Ferres, L., Fuentes-Sep\u00falveda, J., Gagie, T., He, M., and Navarro, G. (2020). Fast and Compact Planar Embeddings. Comput. Geom. Theory Appl., 89.","DOI":"10.1016\/j.comgeo.2020.101630"},{"key":"ref_37","unstructured":"Chakraborty, S., Grossi, R., Sadakane, K., and Rao Satti, S. (2019). Succinct Representation for (Non) Deterministic Finite Automata. arXiv."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/j.is.2013.08.003","article-title":"Compact Representation of Web Graphs with Extended Functionality","volume":"39","author":"Brisaboa","year":"2014","journal-title":"Inf. Syst."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1016\/j.jcss.2011.09.002","article-title":"Ultra-succinct representation of ordered trees with applications","volume":"78","author":"Jansson","year":"2012","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Hucke, D., Lohrey, M., and Benkner, L.S. (2019, January 7\u201312). Entropy Bounds for Grammar-Based Tree Compressors. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849372"},{"key":"ref_41","unstructured":"Ga\u0144czorz, M. (2020, January 10\u201313). Using Statistical Encoding to Achieve Tree Succinctness Never Seen Before. Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Montpellier, France."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Boucher, C., and Thankachan, S.V. (2020). A Comparison of Empirical Tree Entropies. String Processing and Information Retrieval, Springer International Publishing.","DOI":"10.1007\/978-3-030-59212-7"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Rozenberg, G., and Salomaa, A. (1997). Context-Free Graph Grammars. Handbook of Formal Languages: Volume 3 Beyond Words, Springer.","DOI":"10.1007\/978-3-642-59126-6"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.is.2018.03.002","article-title":"Grammar-based graph compression","volume":"76","author":"Maneth","year":"2018","journal-title":"Inf. Syst."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Maneth, S., and Peternek, F. (2020). Constant delay traversal of grammar-compressed graphs with bounded rank. Inf. Comput., 273.","DOI":"10.1016\/j.ic.2020.104520"},{"key":"ref_46","unstructured":"Gawrychowski, P., and Jez, A. (2016, January 15\u201317). LZ77 factorisation of trees. Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), Madras, India."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Freivalds, R., Kwiatkowska, M., and Peleg, D. (2013). Tree Compression with Top Trees. Automata, Languages, and Programming, Springer.","DOI":"10.1007\/978-3-642-39212-2"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Alanko, J., Gagie, T., Navarro, G., and Seelbach Benkner, L. (2019, January 26\u201329). Tunneling on Wheeler Graphs. Proceedings of the 2019 Data Compression Conference (DCC), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2019.00020"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Prezza, N. (2021, January 10\u201313). On Locating Paths in Compressed Tries. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921), Alexandria, VA, USA.","DOI":"10.1137\/1.9781611976465.47"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.tcs.2017.06.016","article-title":"Wheeler graphs: A framework for BWT-based data structures","volume":"698","author":"Gagie","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Backurs, A., and Indyk, P. (2016, January 9\u201311). Which regular expression patterns are hard to match?. Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), New Brunswick, NJ, USA.","DOI":"10.1109\/FOCS.2016.56"},{"key":"ref_52","unstructured":"Equi, M., M\u00e4kinen, V., and Tomescu, A.I. (2020). Conditional Indexing Lower Bounds Through Self-Reducibility. arXiv."},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Equi, M., M\u00e4kinen, V., and Tomescu, A.I. (2020). Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails. arXiv.","DOI":"10.1007\/978-3-030-67731-2_44"},{"key":"ref_54","unstructured":"Equi, M., Grossi, R., M\u00e4kinen, V., and Tomescu, A.I. (2019, January 9\u201312). On the Complexity of String Matching for Graphs. Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP 2019), Patras, Greece."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","article-title":"On the Complexity of K-SAT","volume":"62","author":"Impagliazzo","year":"2001","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_56","doi-asserted-by":"crossref","unstructured":"Potechin, A., and Shallit, J. (2020). Lengths of words accepted by nondeterministic finite automata. Inf. Process. Lett., 162.","DOI":"10.1016\/j.ipl.2020.105993"},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","article-title":"A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications","volume":"348","author":"Williams","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Gibney, D., Hoppenworth, G., and Thankachan, S.V. (2020). Simple Reductions from Formula-SAT to Pattern Matching on Labeled Graphs and Subtree Isomorphism. arXiv.","DOI":"10.1137\/1.9781611976496.26"},{"key":"ref_59","unstructured":"Chatzigiannakis, I., Kaklamanis, C., Marx, D., and Sannella, D. (2018). Tighter Connections Between Formula-SAT and Shaving Logs. Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 9\u201313 July 2018, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik."},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1006\/jagm.1999.1063","article-title":"Pattern matching in hypertext","volume":"35","author":"Amir","year":"2000","journal-title":"J. Algorithms"},{"key":"ref_61","doi-asserted-by":"crossref","unstructured":"Ferragina, P., and Mishra, B. (2014). Algorithms in Stringomics (I): Pattern-Matching against \u201cStringomes\u201d. BioRxiv.","DOI":"10.1101\/001669"},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.jda.2012.10.001","article-title":"Indexing hypertext","volume":"18","author":"Thachuk","year":"2013","journal-title":"J. Discret. Algorithms"},{"key":"ref_63","unstructured":"Manber, U., and Wu, S. (2020, November 10). Approximate String Matching with Arbitrary Costs for Text and Hypertext. Available online: https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/9789812797919_0002."},{"key":"ref_64","unstructured":"Lucchesi, C.L., and Moura, A.V. (1998). Improved approximate pattern matching on hypertext. LATIN\u201998: Theoretical Informatics, Springer."},{"key":"ref_65","doi-asserted-by":"crossref","unstructured":"Alanko, J., D\u2019Agostino, G., Policriti, A., and Prezza, N. (2020, January 5\u20138). Regular Languages meet Prefix Sorting. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, UT, USA.","DOI":"10.1137\/1.9781611975994.55"},{"key":"ref_66","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","article-title":"Linear automaton transformations","volume":"9","author":"Nerode","year":"1958","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_67","unstructured":"Kosaraju, S.R. (November, January 30). Efficient Tree Pattern Matching. Proceedings of the 30th Annual Symposium on Foundations of Computer Science (SFCS\u201989), Triangle Park, NC, USA."},{"key":"ref_68","unstructured":"Ferragina, P., Luccio, F., Manzini, G., and Muthukrishnan, S. (2005, January 23\u201325). Structuring labeled trees for optimal succinctness, and beyond. Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), Pittsburgh, PA, USA."},{"key":"ref_69","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/2629339","article-title":"Optimal Lower and Upper Bounds for Representing Sequences","volume":"11","author":"Belazzougui","year":"2015","journal-title":"ACM Trans. Algorithms"},{"key":"ref_70","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/s00453-010-9443-8","article-title":"Stronger Lempel-Ziv Based Compressed Text Indexing","volume":"62","author":"Arroyuelo","year":"2012","journal-title":"Algorithmica"},{"key":"ref_71","unstructured":"Raman, R., Raman, V., and Rao, S.S. (2002, January 6\u20138). Succinct Indexable Dictionaries with Applications to Encoding K-Ary Trees and Multisets. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902), San Francisco, CA, USA."},{"key":"ref_72","doi-asserted-by":"crossref","unstructured":"Apostolico, A., Crochemore, M., and Park, K. (2005). An Extension of the Burrows Wheeler Transform and Applications to Sequence Comparison and Data Compression. Combinatorial Pattern Matching, Springer.","DOI":"10.1007\/b137128"},{"key":"ref_73","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/j.tcs.2007.07.014","article-title":"An extension of the Burrows\u2014Wheeler transform","volume":"387","author":"Mantaci","year":"2007","journal-title":"Theor. Comput. Sci."},{"key":"ref_74","doi-asserted-by":"crossref","unstructured":"Mantaci, S., Restivo, A., and Sciortino, M. (2005, January 29\u201331). An extension of the Burrows Wheeler transform to k words. Proceedings of the Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1007\/11496656_16"},{"key":"ref_75","doi-asserted-by":"crossref","unstructured":"Raphael, B., and Tang, J. (2012). Succinct de Bruijn Graphs. Algorithms in Bioinformatics, Springer.","DOI":"10.1007\/978-3-642-33122-0"},{"key":"ref_76","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1109\/TCBB.2013.2297101","article-title":"Indexing Graphs for Path Queries with Applications in Genome Research","volume":"11","year":"2014","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_77","doi-asserted-by":"crossref","unstructured":"Sir\u00e9n, J. (2017, January 16\u201317). Indexing variation graphs. Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX), Barcelona, Spain.","DOI":"10.1137\/1.9781611974768.2"},{"key":"ref_78","unstructured":"M\u00e4kinen, V., Cazaux, B., Equi, M., Norri, T., and Tomescu, A.I. (2020). Linear Time Construction of Indexable Founder Block Graphs. arXiv."},{"key":"ref_79","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.tcs.2017.02.020","article-title":"FM-index of alignment with gaps","volume":"710","author":"Na","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"ref_80","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/j.tcs.2015.08.008","article-title":"FM-index of alignment: A compressed index for similar strings","volume":"638","author":"Na","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_81","doi-asserted-by":"crossref","first-page":"1266","DOI":"10.1093\/bioinformatics\/btu014","article-title":"Efficient haplotype matching and storage using the positional Burrows\u2014Wheeler transform (PBWT)","volume":"30","author":"Durbin","year":"2014","journal-title":"Bioinformatics"},{"key":"ref_82","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.is.2014.06.002","article-title":"The wavelet matrix: An efficient wavelet tree for large alphabets","volume":"47","author":"Claude","year":"2015","journal-title":"Inf. Syst."},{"key":"ref_83","unstructured":"Grossi, R., Gupta, A., and Vitter, J.S. (2003, January 12\u201314). High-Order Entropy-Compressed Text Indexes. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903), Baltimore, MD, USA."},{"key":"ref_84","unstructured":"Navarro, G., Sankoff, D., and Zhu, B. (2018). On Undetected Redundancy in the Burrows-Wheeler Transform. Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM 2018), Qingdao, China, 2\u20134 July 2018, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik."},{"key":"ref_85","unstructured":"Grandoni, F., Herman, G., and Sanders, P. (2020). On the Complexity of BWT-Runs Minimization via Alphabet Reordering. Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020), Pisa, Italy, 7\u20139 September 2020, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"key":"ref_86","unstructured":"Bender, M.A., Svensson, O., and Herman, G. (2019). On the Hardness and Inapproximability of Recognizing Wheeler Graphs. Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019), Munich\/Garching, Germany, 9\u201311 September 2019, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik."},{"key":"ref_87","unstructured":"Gibney, D. (2020, January 23\u201325). Wheeler Graph Recognition on 3-NFAs and 4-NFAs. Proceedings of the Open Problem Session, International Workshop on Combinatorial Algorithms, Pisa, France."},{"key":"ref_88","doi-asserted-by":"crossref","unstructured":"Alanko, J., D\u2019Agostino, G., Policriti, A., and Prezza, N. (2020). Wheeler languages. arXiv.","DOI":"10.1016\/j.ic.2021.104820"},{"key":"ref_89","doi-asserted-by":"crossref","unstructured":"Cotumaccio, N., and Prezza, N. (2021). On Indexing and Compressing Finite Automata. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921), ACM, Society for Industrial and Applied Mathematics. to appear.","DOI":"10.1137\/1.9781611976465.153"},{"key":"ref_90","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","article-title":"Finite Automata and Their Decision Problems","volume":"3","author":"Rabin","year":"1959","journal-title":"IBM J. Res. Dev."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/14\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:07:17Z","timestamp":1760159237000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/1\/14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,5]]},"references-count":90,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["a14010014"],"URL":"https:\/\/doi.org\/10.3390\/a14010014","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,1,5]]}}}