Descriptional complexity of iterated uniform finite-state transducers

DOI10.1016/j.ic.2021.104691OpenAlexW2954028849MaRDI QIDQ5918615

Andreas Malcher, Carlo Mereghetti, Martin Kutrib, Beatrice Palano

Publication date: 14 March 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-02387284

zbMATH Keywords

decidabilitystate complexityiterated transducerssweep complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers* ⋮ Sweep complexity revisited ⋮ Freezing 1-Tag Systems with States ⋮ Iterated uniform finite-state transducers on unary languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• Quantum finite automata: advances on Bertoni's ideas
• On the state complexity of reversals of regular languages
• Iterated sequential transducers as language generating devices
• Improved constructions of quantum automata
• Space-bounded reducibility among combinatorial problems
• Complete problems for deterministic polynomial time
• Finite-state transducer cascades to extract named entities in texts.
• Removing nondeterminism in constant height pushdown automata
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• Complexity of Promise Problems on Classical and Quantum Automata
• Behaviours of Unary Quantum Automata
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• On Deterministic Multi-Pass Analysis
• Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height
• ON THE GENERATIVE POWER OF ITERATED TRANSDUCTION
• Computational Complexity of One-Tape Turing Machine Computations
• Probabilistic automata
• One-tape, off-line Turing machine computations
• An introduction to Kolmogorov complexity and its applications
• Descriptional complexity of iterated uniform finite-state transducers
• Trace monoids with idempotent generators and measure-only quantum automata

This page was built for publication: Descriptional complexity of iterated uniform finite-state transducers