scientific article; zbMATH DE number 7228439

DOI10.4230/LIPICS.STACS.2018.48MaRDI QIDQ3304147zbMATH OpenFDO

Authors Michael Luttenberger, Raphaela Palenta, Helmut Seidl

Publication date 5 August 2020

Full work available at URL https://arxiv.org/abs/1702.06698

zbMATH Keywords

combinatorics on wordscontext-free languageslongest common prefix

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Combinatorics on words (68R15)

Recommendations

• scientific article; zbMATH DE number 1786458
• Largest common prefix of a regular tree language
• Largest common prefix of a regular tree language
• scientific article; zbMATH DE number 7315105
• The complexity of computing the number of strings of given length in context-free languages
• Longest common prefixes with \(k\)-errors and applications
• A Polynomial Algorithm for the Inference of Context Free Languages
• Towards a real time algorithm for parameterized longest common prefix computation
• The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages
• Complexity results for prefix grammars

Cites work

• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• Algorithmics on SLP-compressed strings: a survey
• Deciding equivalence of linear tree-to-word transducers in polynomial time
• Learning sequential tree-to-word transducers
• Normal form on linear tree-to-word transducers
• Normalization of sequential top-down tree-to-word transducers
• Solving fixed-point equations by derivation tree analysis
• Uniqueness Theorems for Periodic Functions

Cited in

(3)

• On the balancedness of tree-to-word transducers
• On the Balancedness of Tree-to-Word Transducers
• Largest common prefix of a regular tree language

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304147)