Document Open Access Logo

Dynamic Membership for Regular Languages

Authors Antoine Amarilli , Louis Jachiet, Charles Paperman

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.116.pdf
  • Filesize: 0.82 MB
  • 17 pages

Document Identifiers

Author Details

Antoine Amarilli
  • LTCI, Télécom Paris, Institut Polytechnique de Paris, France
Louis Jachiet
  • LTCI, Télécom Paris, Institut Polytechnique de Paris, France
Charles Paperman
  • Univ. Lille, CNRS, INRIA, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France

Funding

The authors have been partially supported by the ANR project EQUUS ANR-19-CE48-0019. Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 431183758.

Acknowledgements

We thank Jean-Éric Pin and Jorge Almeida for their advice on ZG and SG, and thank the ICALP referees for their helpful feedback.

Cite As Get BibTex

Antoine Amarilli, Louis Jachiet, and Charles Paperman. Dynamic Membership for Regular Languages. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 116:1-116:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.116

Abstract

We study the dynamic membership problem for regular languages: fix a language L, read a word w, build in time O(|w|) a data structure indicating if w is in L, and maintain this structure efficiently under letter substitutions on w. We consider this problem on the unit cost RAM model with logarithmic word length, where the problem always has a solution in O(log|w| / log log|w|) per operation.
We show that the problem is in O(log log|w|) for languages in an algebraically-defined, decidable class QSG, and that it is in O(1) for another such class QLZG. We show that languages not in QSG admit a reduction from the prefix problem for a cyclic group, so that they require Ω(log|w| /log log|w|) operations in the worst case; and that QSG languages not in QLZG admit a reduction from the prefix problem for the multiplicative monoid U₁ = {0, 1}, which we conjecture cannot be maintained in O(1). This yields a conditional trichotomy. We also investigate intermediate cases between O(1) and O(log log|w|).
Our results are shown via the dynamic word problem for monoids and semigroups, for which we also give a classification. We thus solve open problems of the paper of Skovbjerg Frandsen, Miltersen, and Skyum [Skovbjerg Frandsen et al., 1997] on the dynamic word problem, and additionally cover regular languages.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • regular language
  • membership
  • RAM model
  • updates
  • dynamic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Jorge Almeida and Assis Azevedo. Implicit operations on certain classes of semigroups. In Semigroups and their Applications. Springer, 1987. Google Scholar
  2. Antoine Amarilli, Louis Jachiet, and Charles Paperman. Dynamic membership for regular languages, 2021. URL: http://arxiv.org/abs/2003.02576.
  3. Antoine Amarilli and Charles Paperman. Locality and centrality: The variety ZG, 2021. URL: http://arxiv.org/abs/2102.07724.
  4. Karl Auinger. Semigroups with central idempotents. In Algorithmic problems in groups and semigroups. Springer, 2000. Google Scholar
  5. Andrey Balmin, Yannis Papakonstantinou, and Victor Vianu. Incremental validation of XML documents. TODS, 29(4), 2004. URL: http://db.ucsd.edu/wp-content/uploads/pdfs/212.pdf.
  6. David A. Mix Barrington, Kevin J. Compton, Howard Straubing, and Denis Thérien. Regular languages in NC¹. J. Comput. Syst. Sci., 44(3), 1992. URL: https://www.sciencedirect.com/science/article/pii/002200009290014A.
  7. Laura Chaubard, Jean-Eric Pin, and Howard Straubing. First order formulas with modular predicates. In LICS, 2006. URL: https://hal.archives-ouvertes.fr/hal-00112846/document.
  8. Sang Cho and Dung T. Huynh. Finite-automaton aperiodicity is PSPACE-complete. Theoretical Computer Science, 88(1), 1991. URL: https://doi.org/10.1016/0304-3975(91)90075-d.
  9. Raphael Clifford, Allan Grønlund, Kasper Green Larsen, and Tatiana Starikovskaya. Upper and lower bounds for dynamic data structures on strings. In STACS, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.22.
  10. Assis de Azevedo. The join of the pseudovariety J with permutative pseudovarieties. In Lattices, Semigroups, and Universal Algebra. Springer, 1990. Google Scholar
  11. Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, and Søren Skyum. Dynamic algorithms for the Dyck languages. In WADS, 1995. URL: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.4615&rep=rep1&type=pdf.
  12. Michael Fredman and Michael Saks. The cell probe complexity of dynamic data structures. In STOC, 1989. URL: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.453.9085&rep=rep1&type=pdf.
  13. Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey, and Konstantinos Mamouras. Automata theory on sliding windows. In STACS, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.31.
  14. Moses Ganardi, Danny Hucke, and Markus Lohrey. Querying regular languages over sliding windows. In FSTTCS, 2016. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2016.18.
  15. Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding window property testing for regular languages. In ISAAC, 2019. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.6.
  16. Wouter Gelade, Marcel Marquardt, and Thomas Schwentick. The dynamic complexity of formal languages. TOCL, 13(3), 2012. URL: http://arxiv.org/abs/0812.1915.
  17. Kasper Green Larsen, Jonathan Lindegaard Starup, and Jesper Steensgaard. Further unifying the landscape of cell probe lower bounds. In SOSA, 2021. URL: https://epubs.siam.org/doi/pdf/10.1137/1.9781611976472.25.
  18. Yijie Han and Mikkel Thorup. Integer sorting in O(n √log log n) expected time and linear space. In FOCS, 2002. Google Scholar
  19. Thore Husfeldt and Theis Rauhe. Hardness results for dynamic problems by extensions of Fredman and Saks' chronogram method. In ICALP, 1998. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.6315&rep=rep1&type=pdf.
  20. Louis Jachiet. Computing and maintaining the minimum of a set S of integers while allowing updates on S. Theoretical Computer Science Stack Exchange. URL: https://cstheory.stackexchange.com/q/47831 (version: 2020-11-08).
  21. Louis Jachiet. On the complexity of a “list” datastructure in the RAM model. Theoretical Computer Science Stack Exchange. URL: https://cstheory.stackexchange.com/q/46746 (version: 2020-05-01).
  22. Eugene Kirpichov. Incremental regular expressions. . Code available at : https://github.com/jkff/ire, 2012. URL: http://jkff.info/articles/ire/.
  23. Mihai Pǎtraşcu and Corina E Tarniţǎ. On dynamic bit-probe complexity. Theoretical Computer Science, 380(1-2), 2007. URL: https://www.sciencedirect.com/science/article/pii/S0304397507001624.
  24. Mihai Pǎtraşcu and Mikkel Thorup. Randomization does not help searching predecessors. In SODA, 2007. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.208.6464&rep=rep1&type=pdf.
  25. Jean-Éric Pin. Varieties of formal languages. Foundations of Computer Science. Plenum Publishing Corp., New York, 1986. With a preface by M.-P. Schützenberger, Translated from the French by A. Howie. URL: https://doi.org/10.1007/978-1-4613-2215-3.
  26. Jean-Éric Pin. Mathematical foundations of automata theory, 2019. URL: https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf.
  27. John Rhodes. The fundamental lemma of complexity for arbitrary finite semigroups. Bulletin of the American Mathematical Society, 74(6), 1968. URL: https://doi.org/10.1090/s0002-9904-1968-12064-6.
  28. Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier, and Thomas Zeume. Work-sensitive dynamic complexity of formal languages, 2021. URL: http://arxiv.org/abs/2101.08735.
  29. Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. Dynamic word problems. JACM, 44(2), 1997. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.868.4450&rep=rep1&type=pdf.
  30. Howard Straubing. The variety generated by finite nilpotent monoids. Semigroup Forum, 24(1), 1982. URL: https://doi.org/10.1007/bf02572753.
  31. Howard Straubing. Finite semigroup varieties of the form V*D. Journal of Pure and Applied Algebra, 36, 1985. URL: https://www.sciencedirect.com/science/article/pii/0022404985900623.
  32. Robert Endre Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. Journal of Computer and System Sciences, 18(2), 1979. URL: https://doi.org/10.1016/0022-0000(79)90042-4.
  33. Mikkel Thorup. Equivalence between priority queues and sorting. JACM, 54(6), 2007. Google Scholar
  34. Peter van Emde Boas, Robert Kaas, and Erik Zijlstra. Design and implementation of an efficient priority queue. Mathematical systems theory, 10(1), 1976. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact