Visibly Pushdown Transducers with Well-nested Outputs
type: Distribution
access URL: https://hal.science/hal-00988129
format: HTML
issued: 2026-05-05T11:55:25.381020
modified: 2026-05-05T11:55:25.365889

test_moissonnage_selune
type: Agent

Visibly Pushdown Transducers with Well-nested Outputs
type: Dataset
contact point: Organization
  fn: CCSD
keyword: transduction
keyword: infoinfo-flcomputer-science-csformal-languages-and-automata-theory-csfl
keyword: visibly-pushdown-transducers
keyword: infoeu-reposemanticsreport
keyword: nested-words
keyword: reports
landing page: https://hal.science/hal-00988129
description: Visibly pushdown transducers (VPTs) are visibly pushdown automata extended with outputs. They have been introduced to model transformations of nested words, i.e. words with a call/return structure. When outputs are also structured and well nested words, VPTs are a natural formalism to express tree transformations evaluated in streaming. We prove the class of VPTs with well-nested outputs to be decidable in PTIME. Moreover, we show that this class is closed under composition and that its type-checking against visibly pushdown languages is decidable.
issued: 2026-05-05T11:55:25.378863
language: en
modified: 2026-05-05T11:55:25.378869