Forward and backward application of symbolic tree transducers

DOI10.1007/S00236-014-0197-7zbMATH Open1307.68047arXiv1208.5324OpenAlexW2031404106MaRDI QIDQ404011FDOQ404011

Authors: Zoltán Fülöp, Heiko Vogler 

Publication date: 29 August 2014

Published in: Acta Informatica (Search for Journal in Brave)

Abstract: We consider symbolic tree automata (sta) and symbolic tree transducers (stt). We characterize s-recognizable tree languages (which are the tree languages recognizable by sta) in terms of (classical) recognizable tree languages and relabelings. We prove that sta and the recently introduced variable tree automata are incomparable with respect to their recognition power. We define symbolic regular tree grammars and characterize s-regular tree languages in terms of regular tree languages and relabelings. As a consequence, we obtain that s-recognizable tree languages are the same as s-regular tree languages. We show that the syntactic composition of two stt computes the composition of the tree transformations computed by each stt, provided that (1) the first one is deterministic or the second one is linear and (2) the first one is total or the second is nondeleting. We consider forward application and backward application of stt and prove that the backward application of an stt to any s-recognizable tree language yields an s-recognizable tree language. We give a linear stt of which the range is not an s-recognizable tree language. We show that the forward application of simple and linear stt preserves s-recognizability. As a corollary, we obtain that the type checking problem of simple and linear stt and the inverse type checking problem of arbitrary stt is decidable.

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

Recommendations

• Equivalence of symbolic tree transducers
• Symbolic tree automata
• Alphabetic and synchronized tree transducers
• Weighted extended tree transducers
• scientific article; zbMATH DE number 6131600

zbMATH Keywords

XMLcompositionsymbolic computationtree automatonregular tree grammarrelabellingtop-down tree transducertree transducer

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cites Work

• Bottom-up and top-down tree transformations— a comparison
• Symbolic finite state transducers: algorithms and applications
• One-unambiguous regular languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Variable automata over infinite alphabets
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Generalized sequential machine maps
• Mappings and grammars on trees
• Tree acceptors and some of their applications
• Automatic verification of recursive procedures with one integer parameter.
• XML with data values: Typechecking revisited.
• A comparison of pebble tree transducers with macro tree transducers
• An automata model for trees with ordered data values
• Variable tree automata over infinite ranked alphabets
• Composition of top-down and bottom-up tree transductions
• Title not available (Why is that?)
• Rewriting Systems with Data
• Tree Automata over Infinite Alphabets
• Tree generating regular systems

Cited In (6)

• Succinct ordering and aggregation constraints in algebraic array theories
• Weighted unranked tree automata over tree valuation monoids and their characterization by weighted logics
• Symbolic tree automata
• Title not available (Why is that?)
• Symbolic tree transducers
• Title not available (Why is that?)

This page was built for publication: Forward and backward application of symbolic tree transducers

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