Cover Image

Deciding Linear Height and Linear Size-to-Height Increase for Macro Tree Transducers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gallot, Paul, Maneth, Sebastian, Nakano, Keisuke, Peyrat, Charles
Format:	Preprint
Published:	2023
Subjects:	Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Shape Preserving Tree Transducers
by: Gallot, Paul, et al.
Published: (2025)

Deciding whether an Attributed Translation can be realized by a Top-Down Transducer
by: Maneth, Sebastian, et al.
Published: (2023)

Attributed Tree Transducers for Partial Functions
by: Maneth, Sebastian, et al.
Published: (2024)

When is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?
by: Maneth, Sebastian, et al.
Published: (2025)

Reversible Pebble Transducers
by: Dartois, Luc, et al.
Published: (2025)

Slightly Non-Linear Higher-Order Tree Transducers
by: Nguyên, Lê Thành Dũng, et al.
Published: (2024)

Reversible Transducers over Infinite Words
by: Dartois, Luc, et al.
Published: (2024)

Approximate Problems for Finite Transducers
by: Filiot, Emmanuel, et al.
Published: (2025)

Tree transducers of linear size-to-height increase (and the additive conjunction of linear logic)
by: Dartois, Luc, et al.
Published: (2026)

Finite-valued Streaming String Transducers
by: Filiot, Emmanuel, et al.
Published: (2024)

Composing Copyless Streaming String Transducers
by: Alur, Rajeev, et al.
Published: (2022)

Minimizing Streaming String Transducers: An algebraic approach
by: Benalioua, Yahia Idriss, et al.
Published: (2026)

On Decidability and Expressive Power of Fusion Grammars
by: Pshenitsyn, Tikhon
Published: (2023)

Deciding Subtyping for Asynchronous Multiparty Sessions
by: Li, Elaine, et al.
Published: (2024)

Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids
by: Aristote, Quentin
Published: (2024)

On Decidability Timed Automata with 2 Parametric Clocks
by: Bersani, Marcello M., et al.
Published: (2025)

Certified Symbolic Finite Transducers: Formalization and Applications to String Analysis
by: Kan, Shuanglong, et al.
Published: (2025)

A Regular and Complete Notion of Delay for Streaming String Transducers
by: Filiot, Emmanuel, et al.
Published: (2022)

Reachability in One-Dimensional Pushdown Vector Addition Systems is Decidable
by: Bizière, Clotilde, et al.
Published: (2024)

Transducing Language Models
by: Snæbjarnarson, Vésteinn, et al.
Published: (2026)

Do CFLOBDDs Actually Make Use of Linear Structure?
by: Sistla, Meghana Aparna, et al.
Published: (2026)

A Diamond Structure in the Transducer Hierarchy
by: Kaufmann, Noah
Published: (2021)

A Linear-time Simulation of Deterministic $d$-Limited Automata
by: Rubtsov, Alexander
Published: (2023)

Characterizations of Controlled Generation of Right Linear Grammars with Unknown Behaviors
by: Ise, Daihei, et al.
Published: (2024)

The structure of polynomial growth for tree automata/transducers and MSO set queries
by: Gallot, Paul, et al.
Published: (2025)

Transformers as Transducers
by: Strobl, Lena, et al.
Published: (2024)

Cayley Automatic Groups and Numerical Characteristics of Turing Transducers
by: Berdinsky, Dmitry
Published: (2016)

First-Order Intuitionistic Linear Logic and Hypergraph Languages
by: Pshenitsyn, Tikhon
Published: (2025)

Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fields
by: Bell, Jason P., et al.
Published: (2022)

Decidable problems in substitution shifts
by: Béal, Marie-Pierre, et al.
Published: (2021)

Linear Matching of JavaScript Regular Expressions
by: Barrière, Aurèle, et al.
Published: (2023)

Formally Verified Linear-Time Invertible Lexing
by: Chassot, Samuel, et al.
Published: (2025)

Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems
by: Roop, Partha, et al.
Published: (2026)

Planning with Linear Temporal Logic Specifications: Handling Quantifiable and Unquantifiable Uncertainty
by: Yu, Pian, et al.
Published: (2025)

New Insights into the Decidability of Opacity in Timed Automata
by: Deng, Weilin, et al.
Published: (2025)

Decidability and Characterization of Expansivity for Group Cellular Automata
by: Castronuovo, Niccolo', et al.
Published: (2025)

Minimization of Streaming Transducers
by: Bianchini, Christian, et al.
Published: (2026)

Monads, Comonads, and Transducers
by: Stefański, Rafał
Published: (2024)

LTL-D*: Incrementally Optimal Replanning for Feasible and Infeasible Tasks in Linear Temporal Logic Specifications
by: Ren, Jiming, et al.
Published: (2024)

Scalable Tree-based Register Automata Learning
by: Dierl, Simon, et al.
Published: (2024)