Better complexity bounds for cost register automata
From MaRDI portal
Publication:5111238
DOI10.4230/LIPICS.MFCS.2017.24zbMATH Open1435.68138OpenAlexW2940923581MaRDI QIDQ5111238FDOQ5111238
Eric Allender, A. Krebs, Pierre McKenzie
Publication date: 26 May 2020
Full work available at URL: https://doi.org/10.4230/lipics.mfcs.2017.24
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
- Handbook of weighted automata
- Streaming transducers for algorithmic verification of single-pass list-processing programs
- The Theory of Stabilisation Monoids and Regular Cost Functions
- 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
- 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
- Regular combinators for string transformations
- A Generalised Twinning Property for Minimisation of Cost Register Automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (2)
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)
