TY - GEN
T1 - Computing the longest common prefix of a context-free language in polynomial time
AU - Luttenberger, Michael
AU - Palenta, Raphaela
AU - Seidl, Helmut
N1 - Publisher Copyright:
© Michael Luttenberger, Raphaela Palenta, and Helmut Seidl.
PY - 2018/2/2
Y1 - 2018/2/2
N2 - 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 su x, of a context-free language can be computed in polynomial time.
AB - 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 su x, of a context-free language can be computed in polynomial time.
KW - Combinatorics on Words
KW - Context-free Languages
KW - Longest Common Prefix
UR - http://www.scopus.com/inward/record.url?scp=85044507728&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2018.48
DO - 10.4230/LIPIcs.STACS.2018.48
M3 - Conference contribution
AN - SCOPUS:85044507728
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018
A2 - Vallee, Brigitte
A2 - Niedermeier, Rolf
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018
Y2 - 28 February 2018 through 3 March 2018
ER -