scientific article; zbMATH DE number 7561353

DOI10.4230/LIPICS.FSTTCS.2018.48MaRDI QIDQ5090989zbMATH OpenFDO

Authors Adrien Boiret, Radosław Piórkowski, Janusz Schmude

Publication date 21 July 2022

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

zbMATH Keywords

equivalence problemformal languageHilbert's basis theoremMSO transformationsregister automatatransducersunordered trees

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• The problem of equivalent transformations for homogeneous multitape automata
• On the Transition Reduction Problem for Finite Automata
• On the equivalence problem for deterministic multitape automata and transducers
• Equivalence of transducers relative to regular languages
• On equivalence and uniformisation problems for finite transducers
• Equivalence problems for transducers with a bounded number of states
• Revisiting the equivalence problem for finite multitape automata
• On the Decidability of the Equivalence for a Certain Class of Transducers
• Algorithmic aspects of decomposition and equivalence of finite-valued transducers
• Equivalence, reduction and minimization of finite automata over semirings

Cites work

• A proof of Ehrenfeucht's conjecture
• A short solution for the HDT0L sequence equivalence problem
• A survey on decidable equivalence problems for tree transducers
• Equivalence of deterministic top-down tree-to-string transducers is decidable
• Expressiveness of streaming string transducers
• scientific article; zbMATH DE number 5872386 (Why is no real title available?)
• Macro tree transducers
• Macro Tree Translations of Linear Size Increase are MSO Definable
• Mappings and grammars on trees
• Minimizing subsequential transducers: a survey.
• Monadic second-order definable graph transductions: a survey
• Polynomial automata: zeroness and applications
• Regular functions and cost register automata (invited paper)
• The equivalence of finite valued transducers (on HDT0L languages) is decidable

Cited in

(4)

• scientific article; zbMATH DE number 7559390 (Why is no real title available?)
• scientific article; zbMATH DE number 7561615 (Why is no real title available?)
• Characterizing attributed tree translations in terms of macro tree transducers
• Slice closures of indexed languages and word equations with counting constraints

This page was built for publication:

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