Iterated uniform finite-state transducers on unary languages

DOI10.1007/978-3-030-67731-2_16MaRDI QIDQ831808zbMATH OpenOpenAlexFDO

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

Publication date 24 March 2022

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

zbMATH Keywords

cellular automataunary languagesundecidability resultsstate complexityiterated transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Recommendations

• Descriptional complexity of iterated uniform finite-state transducers
• ON THE GENERATIVE POWER OF ITERATED TRANSDUCTION
• Iterated sequential transducers as language generating devices
• Finite automata and unary languages
• Iterating transducers

Cites work

• scientific article; zbMATH DE number 1502111 (Why is no real title available?)
• scientific article; zbMATH DE number 1886333 (Why is no real title available?)
• scientific article; zbMATH DE number 2113950 (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?)
• Cellular automata with limited inter-cell bandwidth
• Complexity of multi-head finite automata: origins and directions
• Descriptional complexity of iterated uniform finite-state transducers
• Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power
• Finite automata and unary languages
• Finite-state transducer cascades to extract named entities in texts.
• Generation of Primes by a One-Dimensional Real-Time Iterative Array
• Iterated sequential transducers as language generating devices
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• ON THE GENERATIVE POWER OF ITERATED TRANSDUCTION
• On Deterministic Multi-Pass Analysis
• Optimal simulations between unary automata
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Signals in one-dimensional cellular automata
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE

Cited in

(6)

• Iterated sequential transducers as language generating devices
• Descriptional complexity of iterated uniform finite-state transducers
• scientific article; zbMATH DE number 1408344 (Why is no real title available?)
• scientific article; zbMATH DE number 7770052 (Why is no real title available?)
• Iterated uniform finite-state transducers on unary languages
• ON THE GENERATIVE POWER OF ITERATED TRANSDUCTION

This page was built for publication: Iterated uniform finite-state transducers on unary languages

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