Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*

DOI10.3233/FI-222113MaRDI QIDQ5089680zbMATH OpenOpenAlexFDO

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

Publication date 14 July 2022

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.15631

zbMATH Keywords

descriptional complexitynondeterminismiterated transducerslanguage hierarchiessweep complexity

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power
• 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

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (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?)
• An introduction to Kolmogorov complexity and its applications
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• Computational Complexity of One-Tape Turing Machine Computations
• Descriptional and computational complexity of finite automata -- a survey
• Descriptional complexity -- an introductory survey
• Descriptional complexity of iterated uniform finite-state transducers
• Descriptional complexity of iterated uniform finite-state transducers
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power
• Finite-state transducer cascades to extract named entities in texts.
• Iterated sequential transducers as language generating devices
• ON THE GENERATIVE POWER OF ITERATED TRANSDUCTION
• On Deterministic Multi-Pass Analysis
• Quantum finite automata: advances on Bertoni's ideas
• Queue automata of constant length
• Space-bounded reducibility among combinatorial problems
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• Trace monoids with idempotent generators and measure-only quantum automata

Cited in

(2)

• scientific article; zbMATH DE number 7770052 (Why is no real title available?)
• Iterated uniform finite-state transducers on unary languages

This page was built for publication: Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*

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