Better complexity bounds for cost register automata

DOI10.1007/s00224-018-9871-4zbMath1435.68137OpenAlexW2771131742MaRDI QIDQ1999991

Andreas Krebs, Eric W. Allender, Pierre McKenzie

Publication date: 27 June 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8066/

zbMATH Keywords

computational complexitycircuit complexityarithmetic circuitstropical semiringcost register automata

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Handbook of weighted automata
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• 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
• Better complexity bounds for cost register automata
• Regular Functions and Cost Register Automata
• Computational Complexity
• Decision Problems for Additive Regular Functions
• Maximal Partition Logic: Towards a Logical Characterization of Copyless Cost Register Automata
• Streaming transducers for algorithmic verification of single-pass list-processing programs

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