2026-07-20T05:10:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8482 2024-03-06T10:42:21Z ddc:004 open_access

Computing the Longest Common Prefix of a Context-free Language in Polynomial Time Luttenberger, Michael Palenta, Raphaela Seidl, Helmut longest common prefix context-free languages combinatorics on words We present two structural results concerning the longest common prefixes of non-empty languages. First, we show that the longest common prefix of the language generated by a context-free grammar of size N equals the longest common prefix of the same grammar where the heights of the derivation trees are bounded by 4N. Second, we show that each non-empty language L has a representative subset of at most three elements which behaves like L w.r.t. the longest common prefix as well as w.r.t. longest common prefixes of L after unions or concatenations with arbitrary other languages. From that, we conclude that the longest common prefix, and thus the longest common suffix, of a context-free language can be computed in polynomial time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Luttenberger and Raphaela Palenta and Helmut Seidl 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.48 urn:nbn:de:0030-drops-84828 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.48 eng https://creativecommons.org/licenses/by/3.0/legalcode