Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power

DOI10.1007/978-3-030-51466-2_8OpenAlexW3038048333MaRDI QIDQ2106594FDOQ2106594

Authors: Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano 

Publication date: 16 December 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-51466-2_8

Recommendations

• Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
• Descriptional complexity of iterated uniform finite-state transducers
• Descriptional complexity of iterated uniform finite-state transducers
• Iterated uniform finite-state transducers on unary languages
• ON THE GENERATIVE POWER OF ITERATED TRANSDUCTION

zbMATH Keywords

state complexityiterated transducerslanguage hierarchiessweep complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• On the power of one-way automata with quantum and classical states
• Title not available (Why is that?)
• Title not available (Why is that?)
• Descriptional complexity -- an introductory survey
• Trace monoids with idempotent generators and measure-only quantum automata
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• Computational Complexity of One-Tape Turing Machine Computations
• Finite-state transducer cascades to extract named entities in texts.
• On Deterministic Multi-Pass Analysis
• ON THE GENERATIVE POWER OF ITERATED TRANSDUCTION
• Descriptional complexity of iterated uniform finite-state transducers
• Iterated sequential transducers as language generating devices
• An introduction to Kolmogorov complexity and its applications

Cited In (3)

• Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
• Iterated uniform finite-state transducers on unary languages
• Title not available (Why is that?)

This page was built for publication: Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power

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