Better complexity bounds for cost register automata

DOI10.4230/LIPICS.MFCS.2017.24MaRDI QIDQ5111238zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 619536 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1163636 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• A generalised twinning property for minimisation of cost register automata
• Complexity of Regular Functions
• Computing Algebraic Formulas Using a Constant Number of Registers
• Copyless cost-register automata: structure, expressiveness, and closure properties
• Cost functions definable by min/max automata
• Cost register automata for nested words
• Decision problems for additive regular functions
• Finite Monoids: From Word to Circuit Evaluation
• Handbook of weighted automata
• Regular combinators for string transformations
• Regular cost functions. I: Logic and algebra over words
• Regular functions and cost register automata (invited paper)
• Straight-line program length as a parameter for complexity analysis
• Streaming transducers for algorithmic verification of single-pass list-processing programs
• The Theory of Stabilisation Monoids and Regular Cost Functions
• The iterated mod problem
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(11)

• Cost register automata for nested words
• A generalised twinning property for minimisation of cost register automata
• Copyless cost-register automata: structure, expressiveness, and closure properties
• Better complexity bounds for cost register automata
• Copyless cost-register automata: structure, expressiveness, and closure properties
• Decision problems for additive regular functions
• Weak cost register automata are still powerful
• Maximal partition logic: towards a logical characterization of copyless cost register automata
• Weak cost register automata are still powerful
• Streamable regular transductions
• Determinisation of finitely-ambiguous copyless cost register automata

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)