References

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