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

DOI10.3233/FI-222113OpenAlexW4282011430MaRDI QIDQ5089680FDOQ5089680

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An introduction to Kolmogorov complexity and its applications
• Title not available (Why is that?)
• Descriptional and computational complexity of finite automata -- a survey
• 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
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• Space-bounded reducibility among combinatorial problems
• Computational Complexity of One-Tape Turing Machine Computations
• Queue automata of constant length
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• Quantum finite automata: advances on Bertoni's ideas
• Finite-state transducer cascades to extract named entities in texts.
• Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power
• 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
• Descriptional complexity of iterated uniform finite-state transducers

Cited In (2)

• Title not available (Why is that?)
• 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)