Better complexity bounds for cost register automata

DOI10.4230/LIPIcs.MFCS.2017.24zbMath1435.68138OpenAlexW2940923581MaRDI QIDQ5111238

Andreas Krebs, Pierre McKenzie, Eric W. Allender

Publication date: 26 May 2020

Full work available at URL: https://doi.org/10.4230/lipics.mfcs.2017.24

zbMATH Keywords

computational complexitycost registers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items

Better complexity bounds for cost register automata ⋮ Streamable regular transductions

Cites Work

• Handbook of weighted automata
• The iterated mod problem
• Straight-line program length as a parameter for complexity analysis
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Complexity of Regular Functions
• Cost Register Automata for Nested Words
• Regular Cost Functions, Part I: Logic and Algebra over Words
• The Theory of Stabilisation Monoids and Regular Cost Functions
• Computing Algebraic Formulas Using a Constant Number of Registers
• Finite Monoids: From Word to Circuit Evaluation
• Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties
• Regular combinators for string transformations
• A Generalised Twinning Property for Minimisation of Cost Register Automata
• Regular Functions and Cost Register Automata
• Decision Problems for Additive Regular Functions
• Streaming transducers for algorithmic verification of single-pass list-processing programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Better complexity bounds for cost register automata