On the Balancedness of Tree-to-Word Transducers

A language over an alphabet [Formula: see text] of opening ([Formula: see text]) and closing ([Formula: see text]) brackets, is balanced if it is a subset of the Dyck language [Formula: see text] over [Formula: see text], and it is well-formed if all words are prefixes of words in [Formula: see text...

Descripción completa

Detalles Bibliográficos
Autores principales: Löbel, Raphaela, Luttenberger, Michael, Seidl, Helmut
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7247909/
http://dx.doi.org/10.1007/978-3-030-48516-0_17
_version_ 1783538262014427136
author Löbel, Raphaela
Luttenberger, Michael
Seidl, Helmut
author_facet Löbel, Raphaela
Luttenberger, Michael
Seidl, Helmut
author_sort Löbel, Raphaela
collection PubMed
description A language over an alphabet [Formula: see text] of opening ([Formula: see text]) and closing ([Formula: see text]) brackets, is balanced if it is a subset of the Dyck language [Formula: see text] over [Formula: see text], and it is well-formed if all words are prefixes of words in [Formula: see text]. We show that well-formedness of a context-free language is decidable in polynomial time, and that the longest common reduced suffix can be computed in polynomial time. With this at a hand we decide for the class 2-TW of non-linear tree transducers with output alphabet [Formula: see text] whether or not the output language is balanced.
format Online
Article
Text
id pubmed-7247909
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72479092020-05-26 On the Balancedness of Tree-to-Word Transducers Löbel, Raphaela Luttenberger, Michael Seidl, Helmut Developments in Language Theory Article A language over an alphabet [Formula: see text] of opening ([Formula: see text]) and closing ([Formula: see text]) brackets, is balanced if it is a subset of the Dyck language [Formula: see text] over [Formula: see text], and it is well-formed if all words are prefixes of words in [Formula: see text]. We show that well-formedness of a context-free language is decidable in polynomial time, and that the longest common reduced suffix can be computed in polynomial time. With this at a hand we decide for the class 2-TW of non-linear tree transducers with output alphabet [Formula: see text] whether or not the output language is balanced. 2020-05-26 /pmc/articles/PMC7247909/ http://dx.doi.org/10.1007/978-3-030-48516-0_17 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Löbel, Raphaela
Luttenberger, Michael
Seidl, Helmut
On the Balancedness of Tree-to-Word Transducers
title On the Balancedness of Tree-to-Word Transducers
title_full On the Balancedness of Tree-to-Word Transducers
title_fullStr On the Balancedness of Tree-to-Word Transducers
title_full_unstemmed On the Balancedness of Tree-to-Word Transducers
title_short On the Balancedness of Tree-to-Word Transducers
title_sort on the balancedness of tree-to-word transducers
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7247909/
http://dx.doi.org/10.1007/978-3-030-48516-0_17
work_keys_str_mv AT lobelraphaela onthebalancednessoftreetowordtransducers
AT luttenbergermichael onthebalancednessoftreetowordtransducers
AT seidlhelmut onthebalancednessoftreetowordtransducers

Ejemplares similares