@inproceedings(AbboudEtAl2015,
 author       = {Amir Abboud and Arturs Backurs and Virginia Vassilevska Williams},
 year         = {2015},
 title        = {Tight Hardness Results for {LCS} and Other Sequence Similarity Measures},
 booktitle    = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015},
 pages        = {59--78},
 doi          = {10.1109/FOCS.2015.14},
)
@inproceedings(AbboudEtAl2014,
 author       = {Amir Abboud and Virginia Vassilevska Williams and Oren Weimann},
 year         = {2014},
 title        = {Consequences of Faster Alignment of Sequences},
 booktitle    = {Automata, Languages, and Programming - 41st International Colloquium, {ICALP} 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part {I}},
 pages        = {39--51},
 doi          = {10.1007/978-3-662-43948-7\_4},
)
@article(amadini2021survey,
 author       = {Roberto Amadini},
 year         = {2021},
 title        = {A survey on string constraint solving},
 journal      = {ACM Computing Surveys (CSUR)},
 volume       = {55},
 number       = {1},
 pages        = {1--38},
 doi          = {10.1145/3484198},
)
@article(Angluin80,
 author       = {Dana Angluin},
 year         = {1980},
 title        = {Finding Patterns Common to a Set of Strings},
 journal      = {J. Comput. Syst. Sci.},
 volume       = {21},
 number       = {1},
 pages        = {46--62},
 doi          = {10.1016/0022-0000(80)90041-0},
)
@inproceedings(ArtikisEtAl2017,
 author       = {Alexander Artikis and Alessandro Margara and Mart{\'{\i}}n Ugarte and Stijn Vansummeren and Matthias Weidlich},
 year         = {2017},
 title        = {Complex Event Recognition Languages: Tutorial},
 booktitle    = {Proceedings of the 11th {ACM} International Conference on Distributed and Event-based Systems, {DEBS} 2017, Barcelona, Spain, June 19-23, 2017},
 pages        = {7--10},
 doi          = {10.1145/3093742.3095106},
)
@article(DBLP:journals/tcs/Baeza-Yates91,
 author       = {Baeza{-}Yates, Ricardo A.},
 year         = {1991},
 title        = {Searching Subsequences},
 journal      = {Theor. Comput. Sci.},
 volume       = {78},
 number       = {2},
 pages        = {363--376},
 doi          = {10.1016/0304-3975(91)90358-9},
)
@inproceedings(Barker2020,
 author       = {Laura Barker and Pamela Fleischmann and Katharina Harwardt and Florin Manea and Dirk Nowotka},
 year         = {2020},
 title        = {Scattered Factor-Universality of Words},
 editor       = {Natasa Jonoska and Dmytro Savchuk},
 booktitle    = {Proc. DLT 2020},
 series       = {Lecture Notes in Computer Science},
 volume       = {12086},
 pages        = {14--28},
 doi          = {10.1007/978-3-030-48516-0_2},
)
@article(BilleEtAl2012,
 author       = {Philip Bille and G{\o}rtz, Inge Li and Vildh{\o}j, Hjalte Wedel and David Kofoed Wind},
 year         = {2012},
 title        = {String matching with variable length gaps},
 journal      = {Theor. Comput. Sci.},
 volume       = {443},
 pages        = {25--34},
 doi          = {10.1016/j.tcs.2012.03.029},
)
@inproceedings(Bringmann2014,
 author       = {Karl Bringmann},
 year         = {2014},
 title        = {Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless {SETH} Fails},
 booktitle    = {55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS} 2014, Philadelphia, PA, USA, October 18-21, 2014},
 pages        = {661--670},
 doi          = {10.1109/FOCS.2014.76},
)
@inproceedings(Bringmann2019,
 author       = {Karl Bringmann},
 year         = {2019},
 title        = {Fine-Grained Complexity Theory (Tutorial)},
 booktitle    = {36th International Symposium on Theoretical Aspects of Computer Science, {STACS} 2019, March 13-16, 2019, Berlin, Germany},
 pages        = {4:1--4:7},
 doi          = {10.4230/LIPIcs.STACS.2019.4},
)
@inproceedings(DBLP:conf/fsttcs/BringmannC18,
 author       = {Karl Bringmann and Bhaskar Ray Chaudhury},
 year         = {2018},
 title        = {Sketching, Streaming, and Fine-Grained Complexity of (Weighted) {LCS}},
 booktitle    = {Proc. {FSTTCS} 2018},
 series       = {LIPIcs},
 volume       = {122},
 pages        = {40:1--40:16},
 doi          = {10.4230/LIPIcs.FSTTCS.2018.40},
)
@inproceedings(BringmannK18,
 author       = {Karl Bringmann and Marvin K{\"{u}}nnemann},
 year         = {2018},
 title        = {Multivariate Fine-Grained Complexity of Longest Common Subsequence},
 booktitle    = {Proc. {SODA} 2018},
 pages        = {1216--1235},
 doi          = {10.1137/1.9781611975031.79},
)
@article(BussSoltys2014,
 author       = {Sam Buss and Michael Soltys},
 year         = {2014},
 title        = {Unshuffling a square is {NP}-hard},
 journal      = {J. Comput. Syst. Sci.},
 volume       = {80},
 number       = {4},
 pages        = {766--776},
 doi          = {10.1016/j.jcss.2013.11.002},
)
@article(CliffordC07,
 author       = {Peter Clifford and Rapha{\"{e}}l Clifford},
 year         = {2007},
 title        = {Simple deterministic wildcard matching},
 journal      = {Inf. Process. Lett.},
 volume       = {101},
 number       = {2},
 pages        = {53--54},
 doi          = {10.1016/j.ipl.2006.08.002},
)
@book(crochemore,
 author       = {Maxime Crochemore and Christophe Hancart and Thierry Lecroq},
 year         = {2007},
 title        = {Algorithms on strings},
 publisher    = {Cambridge University Press},
 doi          = {10.1017/CBO9780511546853},
)
@article(CrochemoreMT03,
 author       = {Maxime Crochemore and Borivoj Melichar and Tron{\'{\i}}cek, Zdenek},
 year         = {2003},
 title        = {Directed acyclic subsequence graph --- Overview},
 journal      = {J. Discrete Algorithms},
 volume       = {1},
 number       = {3-4},
 pages        = {255--280},
 doi          = {10.1016/S1570-8667(03)00029-7},
)
@inproceedings(DayFKKMS21,
 author       = {Joel D. Day and Pamela Fleischmann and Maria Kosche and Ko{\ss}, Tore and Florin Manea and Stefan Siemer},
 year         = {2021},
 title        = {The Edit Distance to k-Subsequence Universality},
 booktitle    = {{STACS}},
 series       = {LIPIcs},
 volume       = {187},
 publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
 pages        = {25:1--25:19},
 doi          = {10.4230/LIPIcs.STACS.2021.25},
)
@article(Day2022,
 author       = {Joel D. Day and Maria Kosche and Florin Manea and Markus L. Schmid},
 year         = {2022},
 title        = {Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems},
 journal      = {CoRR},
 volume       = {abs/2206.13896},
 doi          = {10.48550/ARXIV.2206.13896},
)
@article(DroubayJP01,
 author       = {Xavier Droubay and Jacques Justin and Giuseppe Pirillo},
 year         = {2001},
 title        = {Episturmian words and some constructions of de {L}uca and {R}auzy},
 journal      = {Theor. Comput. Sci.},
 volume       = {255},
 number       = {1-2},
 pages        = {539--553},
 doi          = {10.1016/S0304-3975(99)00320-5},
)
@inproceedings(KufMFCS,
 author       = {Lukas Fleischer and Manfred Kufleitner},
 year         = {2018},
 title        = {Testing {S}imon's congruence},
 booktitle    = {Proc. {MFCS} 2018},
 series       = {LIPIcs},
 volume       = {117},
 pages        = {62:1--62:13},
 doi          = {10.4230/LIPIcs.MFCS.2018.62},
)
@article(FleischmannDCFS2022,
 author       = {Pamela Fleischmann and Sebastian Bernhard Germann and Dirk Nowotka},
 year         = {2021},
 title        = {Scattered Factor Universality - The Power of the Remainder},
 journal      = {CoRR},
 volume       = {abs/2104.09063},
 doi          = {10.48550/ARXIV.2104.09063},
 note         = {To appear in Proc. DCFS 2022},
)
@article(Fleischmann2022,
 author       = {Pamela Fleischmann and Lukas Haschke and Annika Huch and Annika Mayrock and Dirk Nowotka},
 year         = {2022},
 title        = {m-Nearly k-Universal Words - Investigating Simon Congruence},
 journal      = {CoRR},
 volume       = {abs/2202.07981},
 doi          = {10.48550/ARXIV.2202.07981},
)
@article(FreydenbergerGK15,
 author       = {Dominik D. Freydenberger and Pawel Gawrychowski and Juhani Karhum{\"{a}}ki and Florin Manea and Wojciech Rytter},
 year         = {2015},
 title        = {Testing $k$-binomial equivalence},
 journal      = {CoRR abs/1509.00622},
 pages        = {239--248},
 doi          = {10.48550/ARXIV.1509.00622},
 note         = {{\em Multidisciplinary Creativity}, a collection of papers dedicated to G. P\u aun 65th birthday},
)
@phdthesis(Ganardi19,
 author       = {Moses Ganardi},
 year         = {2019},
 title        = {Language recognition in the sliding window model},
 school       = {University of Siegen, Germany},
)
@inproceedings(GanardiHKLM18,
 author       = {Moses Ganardi and Danny Hucke and Daniel K{\"{o}}nig and Markus Lohrey and Konstantinos Mamouras},
 year         = {2018},
 title        = {Automata Theory on Sliding Windows},
 booktitle    = {{STACS}},
 series       = {LIPIcs},
 volume       = {96},
 publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
 pages        = {31:1--31:14},
 doi          = {10.4230/LIPIcs.STACS.2018.31},
)
@inproceedings(GanardiHL16,
 author       = {Moses Ganardi and Danny Hucke and Markus Lohrey},
 year         = {2016},
 title        = {Querying Regular Languages over Sliding Windows},
 booktitle    = {{FSTTCS}},
 series       = {LIPIcs},
 volume       = {65},
 publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
 pages        = {18:1--18:14},
 doi          = {10.4230/LIPIcs.FSTTCS.2016.18},
)
@inproceedings(GanardiHLS19,
 author       = {Moses Ganardi and Danny Hucke and Markus Lohrey and Tatiana Starikovskaya},
 year         = {2019},
 title        = {Sliding Window Property Testing for Regular Languages},
 booktitle    = {{ISAAC}},
 series       = {LIPIcs},
 volume       = {149},
 publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
 pages        = {6:1--6:13},
 doi          = {10.4230/LIPIcs.ISAAC.2019.6},
)
@inproceedings(garelCPM,
 author       = {Emmanuelle Garel},
 year         = {1993},
 title        = {Minimal Separators of Two Words},
 booktitle    = {Proc. CPM 1993},
 series       = {Lecture Notes in Computer Science},
 volume       = {684},
 pages        = {35--53},
 doi          = {10.1007/BFb0029795},
)
@inproceedings(stacs21,
 author       = {Pawel Gawrychowski and Maria Kosche and Ko{\ss}, Tore and Florin Manea and Stefan Siemer},
 year         = {2021},
 title        = {Efficiently Testing Simon's Congruence},
 editor       = {Markus Bl{\"{a}}ser and Benjamin Monmege},
 booktitle    = {38th International Symposium on Theoretical Aspects of Computer Science, {STACS} 2021, March 16-19, 2021, Saarbr{\"{u}}cken, Germany (Virtual Conference)},
 series       = {LIPIcs},
 volume       = {187},
 publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
 pages        = {34:1--34:18},
 doi          = {10.4230/LIPIcs.STACS.2021.34},
)
@article(GiatrakosEtAl2020,
 author       = {Nikos Giatrakos and Elias Alevizos and Alexander Artikis and Antonios Deligiannakis and Minos N. Garofalakis},
 year         = {2020},
 title        = {Complex event recognition in the Big Data era: a survey},
 journal      = {{VLDB} J.},
 volume       = {29},
 number       = {1},
 pages        = {313--352},
 doi          = {10.1007/s00778-019-00557-w},
)
@inproceedings(HalfonSZ17,
 author       = {Simon Halfon and Philippe Schnoebelen and Georg Zetzsche},
 year         = {2017},
 title        = {Decidability, complexity, and expressiveness of first-order logic over the subword ordering},
 booktitle    = {Proc. {LICS} 2017},
 pages        = {1--12},
 doi          = {10.5555/3329995.3330076},
)
@article(TCS::Hebrard1991,
 author       = {Jean-Jacques Hebrard},
 year         = {1991},
 title        = {An algorithm for distinguishing efficiently bit-strings by their subsequences},
 journal      = {Theor. Comput. Sci.},
 volume       = {82},
 number       = {1},
 pages        = {35--49},
 doi          = {10.1016/0304-3975(91)90170-7},
)
@article(ImpagliazzoPaturi2001,
 author       = {Russell Impagliazzo and Ramamohan Paturi},
 year         = {2001},
 title        = {On the Complexity of $k$-{SAT}},
 journal      = {J. Comput. Syst. Sci.},
 volume       = {62},
 number       = {2},
 pages        = {367--375},
 doi          = {10.1006/jcss.2000.1727},
)
@article(ImpagliazzoEtAl2001,
 author       = {Russell Impagliazzo and Ramamohan Paturi and Francis Zane},
 year         = {2001},
 title        = {Which Problems Have Strongly Exponential Complexity?},
 journal      = {J. Comput. Syst. Sci.},
 volume       = {63},
 number       = {4},
 pages        = {512--530},
 doi          = {10.1006/jcss.2001.1774},
)
@article(KarandikarKS15,
 author       = {Prateek Karandikar and Manfred Kufleitner and Philippe Schnoebelen},
 year         = {2015},
 title        = {On the index of {S}imon's congruence for piecewise testability},
 journal      = {Inf. Process. Lett.},
 volume       = {115},
 number       = {4},
 pages        = {515--519},
 doi          = {10.1016/j.ipl.2014.11.008},
)
@inproceedings(CSLKarandikarS,
 author       = {Prateek Karandikar and Philippe Schnoebelen},
 year         = {2016},
 title        = {The Height of Piecewise-Testable Languages with Applications in Logical Complexity},
 booktitle    = {Proc. {CSL} 2016},
 series       = {LIPIcs},
 volume       = {62},
 pages        = {37:1--37:22},
 doi          = {10.4230/LIPIcs.CSL.2016.37},
)
@article(journals/lmcs/KarandikarS19,
 author       = {Prateek Karandikar and Philippe Schnoebelen},
 year         = {2019},
 title        = {The height of piecewise-testable languages and the complexity of the logic of subwords},
 journal      = {Log. Methods Comput. Sci.},
 volume       = {15},
 number       = {2},
 doi          = {10.23638/LMCS-15(2:6)2019},
)
@inproceedings(Kosche2021,
 author       = {Maria Kosche and Ko{\ss}, Tore and Florin Manea and Stefan Siemer},
 year         = {2021},
 title        = {Absent Subsequences in Words},
 editor       = {Paul C. Bell and Patrick Totzke and Igor Potapov},
 booktitle    = {Reachability Problems},
 publisher    = {Springer International Publishing},
 address      = {Cham},
 pages        = {115--131},
 doi          = {10.1007/978-3-030-89716-1_8},
)
@article(KKMP22,
 author       = {Maria Kosche and Tore Koß and Florin Manea and Viktoriya Pak},
 year         = {2022},
 title        = {Subsequences in Bounded Ranges: Matching and Analysis Problems},
 journal      = {CoRR},
 volume       = {abs/2207.09201},
 doi          = {10.48550/ARXIV.2207.09201},
)
@inproceedings(Kuske20,
 author       = {Dietrich Kuske},
 year         = {2020},
 title        = {The Subtrace Order and Counting First-Order Logic},
 booktitle    = {Proc. {CSR} 2020},
 series       = {Lecture Notes in Computer Science},
 volume       = {12159},
 pages        = {289--302},
 doi          = {10.1007/978-3-030-50026-9_21},
)
@inproceedings(KuskeZ19,
 author       = {Dietrich Kuske and Georg Zetzsche},
 year         = {2019},
 title        = {Languages Ordered by the Subword Order},
 booktitle    = {Proc. {FOSSACS} 2019},
 series       = {Lecture Notes in Computer Science},
 volume       = {11425},
 pages        = {348--364},
 doi          = {10.1007/978-3-030-17127-8_20},
)
@inproceedings(Rigo19,
 author       = {Marie Lejeune and Julien Leroy and Michel Rigo},
 year         = {2019},
 title        = {Computing the $k$-binomial Complexity of the {T}hue-{M}orse Word},
 booktitle    = {Proc. {DLT} 2019},
 series       = {Lecture Notes in Computer Science},
 volume       = {11647},
 pages        = {278--291},
 doi          = {10.1007/978-3-030-24886-4_21},
)
@article(LeroyRS17a,
 author       = {Julien Leroy and Michel Rigo and Manon Stipulanti},
 year         = {2017},
 title        = {Generalized {P}ascal triangle for binomial coefficients of words},
 journal      = {Electron. J. Combin.},
 volume       = {24},
 number       = {1.44},
 pages        = {36 pp.},
 doi          = {10.1016/j.aam.2016.04.006},
)
@article(LokshtanovEtAl2011,
 author       = {Daniel Lokshtanov and D{\'{a}}niel Marx and Saket Saurabh},
 year         = {2011},
 title        = {Lower bounds based on the Exponential Time Hypothesis},
 journal      = {Bull. {EATCS}},
 volume       = {105},
 pages        = {41--72},
 doi          = {10.1007/978-3-319-21275-3_14},
 url          = {http://eatcs.org/beatcs/index.php/beatcs/article/view/92},
)
@article(LucaGZ08,
 author       = {Aldo de Luca and Amy Glen and Luca Q. Zamboni},
 year         = {2008},
 title        = {Rich, Sturmian, and trapezoidal words},
 journal      = {Theor. Comput. Sci.},
 volume       = {407},
 number       = {1-3},
 pages        = {569--573},
 doi          = {10.1016/j.tcs.2008.06.009},
)
@article(Maier:1978,
 author       = {David Maier},
 year         = {1978},
 title        = {The Complexity of Some Problems on Subsequences and Supersequences},
 journal      = {J. ACM},
 volume       = {25},
 number       = {2},
 pages        = {322--336},
 doi          = {10.1145/322063.322075},
)
@article(Mat04,
 author       = {Alexandru Mateescu and Arto Salomaa and Sheng Yu},
 year         = {2004},
 title        = {Subword Histories and {P}arikh Matrices},
 journal      = {J. Comput. Syst. Sci.},
 volume       = {68},
 number       = {1},
 pages        = {1--21},
 doi          = {10.1016/j.jcss.2003.04.001},
)
@article(Riddle1979a,
 author       = {William E. Riddle},
 year         = {1979},
 title        = {An Approach to Software System Modelling and Analysis},
 journal      = {Comput. Lang.},
 volume       = {4},
 number       = {1},
 pages        = {49--66},
 doi          = {10.1016/0096-0551(79)90009-2},
)
@article(RigoS15,
 author       = {Michel Rigo and Pavel Salimov},
 year         = {2015},
 title        = {Another generalization of abelian equivalence: Binomial complexity of infinite words},
 journal      = {Theor. Comput. Sci.},
 volume       = {601},
 pages        = {47--57},
 doi          = {10.1016/j.tcs.2015.07.025},
)
@article(Salomaa05,
 author       = {Arto Salomaa},
 year         = {2005},
 title        = {Connections Between Subwords and Certain Matrix Mappings},
 journal      = {Theoret. Comput. Sci.},
 volume       = {340},
 number       = {2},
 pages        = {188--203},
 doi          = {10.1016/j.tcs.2005.03.024},
)
@article(Seki12,
 author       = {Shinnosuke Seki},
 year         = {2012},
 title        = {Absoluteness of subword inequality is undecidable},
 journal      = {Theor. Comput. Sci.},
 volume       = {418},
 pages        = {116--120},
 doi          = {10.1016/j.tcs.2011.10.017},
)
@article(Shaw1978,
 author       = {Alan C. Shaw},
 year         = {1978},
 title        = {Software Descriptions with Flow Expressions},
 journal      = {{IEEE} Trans. Software Eng.},
 volume       = {4},
 number       = {3},
 pages        = {242--254},
 doi          = {10.1109/TSE.1978.231501},
)
@article(SimonUnpublished,
 author       = {Imre Simon},
 title        = {An Algorithm to Distinguish Words efficiently by their Subwords},
 journal      = {unpublished},
)
@phdthesis(simonPhD,
 author       = {Imre Simon},
 year         = {1972},
 title        = {Hierarchies of events with dot-depth one},
)
@inproceedings(Simon72,
 author       = {Imre Simon},
 year         = {1975},
 title        = {Piecewise testable events},
 booktitle    = {Autom.\ Theor.\ Form.\ Lang., 2nd GI Conf.},
 series       = {LNCS},
 volume       = {33},
 pages        = {214--222},
 doi          = {10.1007/3-540-07407-4_23},
)
@inproceedings(SimonWords,
 author       = {Imre Simon},
 year         = {2003},
 title        = {Words distinguished by their subwords (extended Abstract)},
 booktitle    = {Proc. {WORDS} 2003},
 series       = {TUCS General Publication},
 volume       = {27},
 pages        = {6--13},
)
@inproceedings(DBLP:conf/wia/Tronicek02,
 author       = {Tron{\'{\i}}cek, Zdenek},
 year         = {2002},
 title        = {Common Subsequence Automaton},
 booktitle    = {Proc. {CIAA} 2002 (Revised Papers)},
 series       = {Lecture Notes in Computer Science},
 volume       = {2608},
 pages        = {270--275},
 doi          = {10.1007/3-540-44977-9_28},
)
@article(Tzeng1992,
 author       = {Wen{-}Guey Tzeng},
 year         = {1992},
 title        = {A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata},
 journal      = {{SIAM} J. Comput.},
 volume       = {21},
 number       = {2},
 pages        = {216--227},
 doi          = {10.1137/0221017},
)
@inproceedings(Williams2015,
 author       = {Virginia Vassilevska Williams},
 year         = {2015},
 title        = {Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)},
 booktitle    = {10th International Symposium on Parameterized and Exact Computation, {IPEC} 2015, September 16-18, 2015, Patras, Greece},
 pages        = {17--29},
 doi          = {10.4230/LIPIcs.IPEC.2015.17},
)
@inproceedings(Zetzsche16,
 author       = {Georg Zetzsche},
 year         = {2016},
 title        = {The Complexity of Downward Closure Comparisons},
 booktitle    = {Proc. {ICALP} 2016},
 series       = {LIPIcs},
 volume       = {55},
 pages        = {123:1--123:14},
 doi          = {10.4230/LIPIcs.ICALP.2016.123},
)
@inproceedings(ZhangEtAl2014,
 author       = {Haopeng Zhang and Yanlei Diao and Neil Immerman},
 year         = {2014},
 title        = {On complexity and optimization of expensive queries in complex event processing},
 booktitle    = {International Conference on Management of Data, {SIGMOD} 2014, Snowbird, UT, USA, June 22-27, 2014},
 pages        = {217--228},
 doi          = {10.1145/2588555.2593671},
)