Balancedness of MSO transductions in polynomial time

DOI10.1016/j.ipl.2018.01.002zbMath1426.68150OpenAlexW2794071377MaRDI QIDQ1705700

Helmut Seidl, Sebastian Maneth

Publication date: 16 March 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.01.002

zbMATH Keywords

formal languagescontext-free languagesMSO-definable transductionsDyck languagesbalanced parentheses

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

On the Balancedness of Tree-to-Word Transducers ⋮ On the Balancedness of Tree-to-Word Transducers

Cites Work

• Unnamed Item
• Tree transducers, L systems, and two-way machines
• Haskell overloading is DEXPTIME-complete
• Formal properties of XML grammars and languages
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Top-down tree transducers with regular look-ahead
• XML Validation for Context-Free Grammars
• On Context-Free Languages
• A characterization of parenthesis languages
• Translations on a context free grammar
• Complexity Results on Balanced Context-Free Languages

This page was built for publication: Balancedness of MSO transductions in polynomial time