On the balancedness of tree-to-word transducers

DOI10.1007/978-3-030-48516-0_17MaRDI QIDQ5041263zbMATH OpenOpenAlexFDO

Authors Raphaela Löbel, Michael Luttenberger, Helmut Seidl

Publication date 13 October 2022

Published in Developments in Language Theory (Search for Journal in Brave)

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

zbMATH Keywords

balancedness of tree-to-word transducerequivalencelongest common suffix/prefix of a CFG

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the Balancedness of Tree-to-Word Transducers
• Balancedness of MSO transductions in polynomial time
• Deciding equivalence of linear tree-to-word transducers in polynomial time
• scientific article; zbMATH DE number 148020
• Balance of many-valued transductions and equivalence problems

Cites work

• A characterization of parenthesis languages
• Algorithmics on SLP-compressed strings: a survey
• Balancedness of MSO transductions in polynomial time
• Complexity Results on Balanced Context-Free Languages
• Derivation tree analysis for accelerated fixed-point computation
• Elements of automata theory. Translated from the French by Reuben Thomas
• Equivalence of deterministic top-down tree-to-string transducers is decidable
• Formal properties of XML grammars and languages
• scientific article; zbMATH DE number 7228439 (Why is no real title available?)
• Visibly pushdown transducers with well-nested outputs
• XML Validation for Context-Free Grammars

Cited in

(2)

• On the Balancedness of Tree-to-Word Transducers
• Balanced-by-construction regular and -regular languages

This page was built for publication: On the balancedness of tree-to-word transducers

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