Balancedness of MSO transductions in polynomial time
type: Item
instance of: scholarly article
title: Balancedness of MSO transductions in polynomial time
zbMATH Open document ID: 1426.68150
published in: Information Processing Letters
publication date: 2018-03-16T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6851035
zbMATH Keywords: balanced parentheses
zbMATH Keywords: Dyck languages
zbMATH Keywords: context-free languages
zbMATH Keywords: MSO-definable transductions
zbMATH Keywords: formal languages
author: Sebastian Maneth
author: Helmut Seidl
MaRDI profile type: Publication
full work available at URL: j.ipl.2018.01.002
OpenAlex ID: W2794071377
cites work: Translations on a context free grammar
cites work: Formal properties of XML grammars and languages
cites work: A comparison of tree transductions defined by monadic second order logic and by attribute grammars
cites work: Q3077955
cites work: Top-down tree transducers with regular look-ahead
cites work: Macro tree transducers, attribute grammars, and MSO definable tree translations.
cites work: Tree transducers, L systems, and two-way machines
cites work: A characterization of parenthesis languages
cites work: XML Validation for Context-Free Grammars
cites work: On Context-Free Languages
cites work: Haskell overloading is DEXPTIME-complete
cites work: Complexity Results on Balanced Context-Free Languages
DOI: 10.1016/J.IPL.2018.01.002
Recommended article: On the complexity of balanced Boolean functions
Recommended article: A POLYNOMIAL TIME ALGORITHM TO DETERMINE MAXIMAL BALANCED EQUIVALENCE RELATIONS
Recommended article: Balance of many-valued transductions and equivalence problems
Recommended article: Q5068890
Recommended article: The equivalence problem for deterministic MSO tree transducers is decidable
Recommended article: FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
Recommended article: On subword decomposition and balanced polynomials
Recommended article: Recognition of tractable satisfiability problems through balanced polynomial representations
Recommended article: The class of 1-balanced functions and the complexity of its realization
description: scientific article; zbMATH DE number 6851035