Document Open Access Logo

Separability by Short Subsequences and Subwords

Authors Piotr Hofman, Wim Martens

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2015.230.pdf
  • Filesize: 479 kB
  • 17 pages

Document Identifiers

Author Details

Piotr Hofman
Wim Martens

Cite As Get BibTex

Piotr Hofman and Wim Martens. Separability by Short Subsequences and Subwords. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 230-246, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.ICDT.2015.230

Abstract

The separability problem for regular languages asks, given two regular languages I and E, whether there exists a language S that separates the two, that is, includes I but contains nothing from E. Typically, S comes from a simple, less expressive class of languages than I and E. In general, a simple separator $S$ can be seen as an approximation of I or as an explanation of how I and E are different. In a database context, separators can be used for explaining the result of regular path queries or for finding explanations for the difference between paths in a graph database, that is, how paths from given nodes u_1 to v_1 are different from those from u_2 to v_2. We study the complexity of separability of regular languages by combinations of subsequences or subwords of a given length k. The rationale is that the parameter k can be used to influence the size and simplicity of the separator. The emphasis of our study is on tracing the tractability of the problem.

Subject Classification

Keywords
  • separability
  • complexity
  • graph data
  • debugging

Metrics

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

References

  1. E. Botoeva, R. Kontchakov, V. Ryzhikov, F. Wolter, and M. Zakharyaschev. Query inseparability for description logic knowledge bases. In Principles of Knowledge Representation and Reasoning (KR), 2014. Google Scholar
  2. J. Brzozowski and I. Simon. Characterizations of locally testable events. Discrete Mathematics, 4(3):243-271, 1973. Google Scholar
  3. P. Buneman and W. C. Tan. Provenance in databases. In International Conference on Management of Data (SIGMOD), pages 1171-1173, 2007. Google Scholar
  4. W. Craig. Three uses of the herbrand-gentzen theorem in relating model theory and proof theory. The Journal of Symbolic Logic, 22(3), 1957. Google Scholar
  5. W. Czerwinski, W. Martens, and T. Masopust. Efficient separability of regular languages by subsequences and suffixes. In International Conference on Automata, Languages and Programming (ICALP), pages 150-161, 2013. Google Scholar
  6. T. A. Henzinger, R. Jhala, R. Majumdar, and K. L. McMillan. Abstractions from proofs. In Principles of Programming Languages (POPL), pages 232-244, 2004. Google Scholar
  7. E. Kopczynski and A. Widjaja To. Parikh images of grammars: Complexity and applications. In Logic in Computer Science (LICS), pages 80-89, 2010. Google Scholar
  8. C. Lutz and F. Wolter. Foundations for uniform interpolation and forgetting in expressive description logics. In International Joint Conference on Artificial Intelligence (IJCAI), pages 989-995, 2011. Google Scholar
  9. T. Masopust and M. Thomazo. On k-piecewise testability (preliminary report). CoRR, abs/1412.1641, 2014. Google Scholar
  10. K. L. McMillan. Applications of craig interpolants in model checking. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pages 1-12, 2005. Google Scholar
  11. R. McNaughton. Algebraic decision procedures for local testability. Mathematical Systems Theory, 8(1):60-76, 1974. Google Scholar
  12. R. McNaughton and S. Papert. Counter-free automata. The M.I.T. Press, 1971. Google Scholar
  13. R. Paige and R. Tarjan. Three parition refinement algorithms. SIAM Journal on Computing, 16:973-989, 1987. Google Scholar
  14. T. Place, L. van Rooijen, and M. Zeitoun. Separating regular languages by locally testable and locally threshold testable languages. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 363-375, 2013. Google Scholar
  15. T. Place, L. van Rooijen, and M. Zeitoun. Separating regular languages by piecewise testable and unambiguous languages. In Mathematical Foundations of Computer Science (MFCS), pages 729-740, 2013. Google Scholar
  16. T. Place and M. Zeitoun. Separating regular languages with first-order logic. In Computer Science Logic - Logic in Computer Science (CSL-LICS), 2014. Google Scholar
  17. L. Van Rooijen. Une approche combinatoire du problème de séparation pour les langages réguliers. PhD thesis, Université de Bordeaux, 2014. Google Scholar
  18. S. Roy and D. Suciu. A formal approach to finding explanations for database queries. In International Conference on Management of Data (SIGMOD), pages 1579-1590, 2014. Google Scholar
  19. I. Simon. Hierarchies of Events with Dot-Depth One. PhD thesis, Dept. of Applied Analysis and Computer Science, University of Waterloo, Canada, 1972. Google Scholar
  20. I. Simon. Piecewise testable events. In Proceedings of GI Conference on Automata Theory and Formal Languages, pages 214-222. Springer, 1975. Google Scholar
  21. J. Stern. Complexity of some problems from the theory of automata. Information and Control, 66(3):163-176, 1985. Google Scholar
  22. L. Stockmeyer and A. Meyer. Word problems requiring exponential time: Preliminary report. In Symposium on Theory of Computing (STOC), pages 1-9, 1973. Google Scholar
  23. W. C. Tan. Provenance in databases: Past, current, and future. IEEE Data Engineering Bulletin, 30(4):3-12, 2007. Google Scholar
  24. Š. Holub, G. Jirśková, and T. Masopust. On upper and lower bounds on the length of alternating towers. In Mathematical Foundations of Computer Science (MFCS), Part I, pages 315-326, 2014. Google Scholar
  25. P. T. Wood. Containment for XPath fragments under DTD constraints. In International Conference on Database Theory (ICDT), 2003. Full version, obtained through personal communication. Google Scholar
  26. Y. Zalcstein. Locally testable languages. Journal of Computer and System Sciences, 6(2):151-167, 1972. 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