Document Open Access Logo

Local Patterns

Authors Joel D. Day, Pamela Fleischmann, Florin Manea, Dirk Nowotka

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.24.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Joel D. Day
Pamela Fleischmann
Florin Manea
Dirk Nowotka

Cite As Get BibTex

Joel D. Day, Pamela Fleischmann, Florin Manea, and Dirk Nowotka. Local Patterns. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.24

Abstract

A pattern is a word consisting of constants from an alphabet Sigma of terminal symbols and variables from a set X. Given a pattern alpha, the decision-problem whether a given word w may be obtained by substituting the variables in \alpha for words over Sigma is called the matching problem. While this problem is, in general, NP-complete, several classes of patterns for which it can be efficiently solved are already known. We present two new classes of patterns, called k-local, and strongly-nested, and show that the respective matching problems, as well as membership can be solved efficiently for any fixed k.

Subject Classification

Keywords
  • Patterns with Variables
  • Local Patterns
  • Combinatorial Pattern Matching
  • Descriptive Patterns

Metrics

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

References

  1. Amihood Amir and Igor Nor. Generalized function matching. Journal of Discrete Algorithms, 5:514-523, 2007. Google Scholar
  2. Dana Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21:46-62, 1980. Google Scholar
  3. Pablo Barceló, Leonid Libkin, Anthony W. Lin, and Peter T. Wood. Expressive languages for path queries over graph-structured data. ACM Transactions on Database Systems, 37, 2012. Google Scholar
  4. Cezar Câmpeanu, Kai Salomaa, and Sheng Yu. A formal study of practical regular expressions. International Journal of Foundations of Computer Science, 14:1007-1018, 2003. Google Scholar
  5. Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, and Thomas Zeugmann. Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries. Theoretical Computer Science, 261:119-156, 2001. Google Scholar
  6. Henning Fernau, Florin Manea, Robert Mercaş, and Markus L. Schmid. Pattern matching with variables: Fast algorithms and new hardness results. In Proc. 32nd Symposium on Theoretical Aspects of Computer Science, STACS 2015, volume 30 of Leibniz International Proceedings in Informatics (LIPIcs), pages 302-315, 2015. Google Scholar
  7. Henning Fernau, Florin Manea, Robert Mercaş, and Markus L. Schmid. Revisiting Shinohara’s algorithm for computing descriptive patterns. Theoretical Computer Science, 2016. Accepted for publication. Preliminary version: http://www.informatik.uni-trier.de/~schmid/preprints/journals/2017_TCS_preprint.pdf .
  8. Henning Fernau and Markus L. Schmid. Pattern matching with variables: A multivariate complexity analysis. Information and Computation, 242:287-305, 2015. Google Scholar
  9. Henning Fernau, Markus L. Schmid, and Yngve Villanger. On the parameterised complexity of string morphism problems. Theory of Computing Systems, 2015. Google Scholar
  10. Dominik D. Freydenberger. Extended regular expressions: Succinctness and decidability. Theory of Computing Systems, 53:159-193, 2013. Google Scholar
  11. Dominik D. Freydenberger and Daniel Reidenbach. Inferring descriptive generalisations of formal languages. Journal of Computer and System Sciences, 79:622-639, 2013. Google Scholar
  12. Jeffrey E. F. Friedl. Mastering Regular Expressions. O'Reilly, Sebastopol, CA, third edition, 2006. Google Scholar
  13. Juhani Karhumäki, Wojciech Plandowski, and Filippo Mignosi. The expressibility of languages and relations by word equations. Journal of the ACM, 47:483-505, 2000. Google Scholar
  14. Michael Kearns and Leonard Pitt. A polynomial-time algorithm for learning k-variable pattern languages from examples. In Proceedings of the 2nd Annual Conference on Learning Theory, COLT, pages 57-71, 1989. Google Scholar
  15. Satoshi Kobayashi and Takashi Yokomori. On approximately identifying concept classes in the limit. In Proceedings of the 6th International Conference on Algorithmic Learning Theory, ALT, volume 997 of LNCS, pages 298-312, 1995. Google Scholar
  16. Dmitry Kosolobov, Florin Manea, and Dirk Nowotka. Detecting one-variable patterns. CoRR, abs/1604.00054, 2016. to appear in SPIRE 2017. Google Scholar
  17. Stefan Lange and Rolf Wiehagen. Polynomial-time inference of arbitrary pattern languages. New Generation Computing, 8:361-370, 1991. Google Scholar
  18. M. Lothaire. Combinatorics on Words. Cambridge University Press, 1997. Google Scholar
  19. M. Lothaire. Algebraic Combinatorics on Words. Cambridge University Press, 2002. Google Scholar
  20. Alexandru Mateescu and Arto Salomaa. Finite degrees of ambiguity in pattern languages. RAIRO Informatique Théoretique et Applications, 28:233-253, 1994. Google Scholar
  21. Zeinab Mazadi, Ziyuan Gao, and Sandra Zilles. Distinguishing pattern languages with membership examples. In Proceedings of the 8th International Conference on Language and Automata Theory and Applications, LATA, volume 8370 of LNCS, pages 528-540, 2014. Google Scholar
  22. Yen K. Ng and Takeshi Shinohara. Developments from enquiries into the learnability of the pattern languages from positive data. Theoretical Computer Science, 397:150-165, 2008. Google Scholar
  23. Sebastian Ordyniak and Alexandru Popa. A parameterized study of maximum generalized pattern matching problems. In Proceedings of the 9th International Symposium on Parameterized and Exact Computation, IPEC, 2014. Google Scholar
  24. Daniel Reidenbach. Discontinuities in pattern inference. Theoretical Computer Science, 397:166-193, 2008. Google Scholar
  25. Daniel Reidenbach and Markus L. Schmid. Patterns with bounded treewidth. Information and Computation, 239:87-99, 2014. Google Scholar
  26. Rüdiger Reischuk and Thomas Zeugmann. Learning one-variable pattern languages in linear average time. In Proceedings of the 11th Annual Conference on Computational Learning Theory, COLT, pages 198-208, 1998. Google Scholar
  27. Markus L. Schmid. A note on the complexity of matching patterns with variables. Information Processing Letters, 113(19):729-733, 2013. Google Scholar
  28. Takeshi Shinohara. Polynomial time inference of pattern languages and its application. In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science, MFCS, pages 191-209, 1982. Google Scholar
  29. Takeshi Shinohara and Setsuo Arikawa. Pattern inference. In K.P. Jantke and S. Lange, editors, Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report, volume 961 of LNAI, pages 259-291, 1995. Google Scholar
  30. Takeshi Shinohara and Hiroki Arimura. Inductive inference of unbounded unions of pattern languages from positive data. Theoretical Computer Science, 241:191-209, 2000. 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