Balancedness of MSO transductions in polynomial time

S. Maneth, H. Seidl

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

We show that MSO definable tree-to-string transductions with a fixed copy number, given as top-down tree-to-string transducers with fixed copying-bound, can be checked for balancedness of all output strings in polynomial time. We also present an upper bound for the copying bound for deterministic top-down transducers and show that in general, balancedness of output languages of deterministic finite-copying top-down tree-to-string transducers is DEXPTIME-hard.

Original languageEnglish
Pages (from-to)26-32
Number of pages7
JournalInformation Processing Letters
Volume133
DOIs
StatePublished - May 2018

Keywords

  • Balanced parentheses
  • Context-free languages
  • Dyck languages
  • Formal languages
  • MSO definable transductions

Fingerprint

Dive into the research topics of 'Balancedness of MSO transductions in polynomial time'. Together they form a unique fingerprint.

Cite this