Finite-state complexity and the size of transducers

zbMATH Open1455.68084arXiv1008.1667MaRDI QIDQ4964008FDOQ4964008

Authors: Kai Salomaa, Tania K. Roblot, Cristian S. Calude 

Publication date: 24 February 2021

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

Recommendations

• State-size hierarchy for finite-state complexity
• Finite state complexity
• Finite state incompressible infinite sequences
• Finite State Incompressible Infinite Sequences
• scientific article; zbMATH DE number 1045406

zbMATH Keywords

descriptional complexitycomputabilityfinite transducersstate-size hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cited In (14)

• Complexity of injection structures induced by finite state transducers
• Descriptional complexity of iterated uniform finite-state transducers
• Finite state complexity
• Algorithmic information theory and computational complexity
• A linearly computable measure of string complexity
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
• The complexity of optimizing finite-state transducers
• State-size hierarchy for finite-state complexity
• Title not available (Why is that?)
• Finite State Transducers with Intuition
• Title not available (Why is that?)
• Lower bounds on the area of finite-state machines
• Implementation and Application of Automata
• State-complexity of finite-state devices, state compressibility and incompressibility

This page was built for publication: Finite-state complexity and the size of transducers

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