Better complexity bounds for cost register automata

DOI10.4230/LIPICS.MFCS.2017.24zbMATH Open1435.68138OpenAlexW2940923581MaRDI QIDQ5111238FDOQ5111238

Authors: A. Krebs, Pierre McKenzie, Eric Allender 

Publication date: 26 May 2020

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

Recommendations

• Better complexity bounds for cost register automata
• Copyless cost-register automata: structure, expressiveness, and closure properties
• Copyless cost-register automata: structure, expressiveness, and closure properties
• Weak cost register automata are still powerful
• Weak cost register automata are still powerful

zbMATH Keywords

computational complexitycost registers

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Better complexity bounds for cost register automata
• Streamable regular transductions

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

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