Polyregular functions: characterisations and refutations

DOI10.1007/978-3-031-66159-4_2MaRDI QIDQ7034846zbMATH OpenFDO

Authors Sandra Kiefer

Publication date 31 January 2025

Full work available at URL https://doi.org/10.1007/978-3-031-66159-4_2

zbMATH Keywords

pebble transducerspolyregular functionsMSO interpretations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3566194 (Why is no real title available?)
• scientific article; zbMATH DE number 1929941 (Why is no real title available?)
• A comparison of pebble tree transducers with macro tree transducers
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Folding interpretations
• Hiding pebbles when the output alphabet is unary
• On non-determinacy in simple computing devices
• On the growth rates of polyregular functions
• Outils et résultats pour les transducteurs boustrophédons
• Output string languages of compositions of deterministic macro tree transducers
• Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
• String-to-string interpretations with polynomial-size output
• The many facets of string transducers (invited talk)
• Two-way pebble transducers for partial functions and their composition
• Typechecking for XML transformers
• XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
• \( \mathbb{Z} \)-polyregular functions

This page was built for publication: Polyregular functions: characterisations and refutations

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