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

DOI10.1007/978-3-030-51466-2_8MaRDI QIDQ2106594zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

iterated transducerslanguage hierarchiesstate complexitysweep complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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

Cites work

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

Cited in

(8)

• Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
• Descriptional complexity of iterated uniform finite-state transducers
• scientific article; zbMATH DE number 7770052 (Why is no real title available?)
• On a simulation of non-inserting accepting networks of evolutionary processors by length preserving iterated uniform finite state transducers
• Latvian quantum finite state automata for unary languages
• Latvian quantum finite state automata for unary languages
• Deterministic pushdown automata with translucent input letters
• Iterated uniform finite-state transducers on unary languages

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)