Finite-state complexity and the size of transducers

MaRDI QIDQ4964008zbMATH OpenFDO

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, http://eptcs.web.cse.unsw.edu.au/paper.cgi?DCFS2010.6

zbMATH Keywords

descriptional complexitycomputabilityfinite transducersstate-size hierarchy

Mathematics Subject Classification ID

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

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

Cited in

(14)

• State-complexity of finite-state devices, state compressibility and incompressibility
• 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
• scientific article; zbMATH DE number 2201359 (Why is no real title available?)
• Finite State Transducers with Intuition
• scientific article; zbMATH DE number 2201358 (Why is no real title available?)
• Lower bounds on the area of finite-state machines
• Implementation and Application of Automata

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)