Descriptional complexity of iterated uniform finite-state transducers
From MaRDI portal
Publication:5918615
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
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
