Better complexity bounds for cost register automata
type: Item
instance of: scholarly article
zbMATH Open document ID: 1435.68138
author: A. Krebs
author: Pierre McKenzie
author: Eric Allender
publication date: 2020-05-26T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q06
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7204358
zbMATH Keywords: computational complexity
zbMATH Keywords: cost registers
MaRDI profile type: MaRDI publication profile
cites work: Complexity of Regular Functions
cites work: Q5465356
cites work: Streaming transducers for algorithmic verification of single-pass list-processing programs
cites work: Regular Functions and Cost Register Automata
cites work: Regular combinators for string transformations
cites work: Decision Problems for Additive Regular Functions
cites work: Q4302457
cites work: Finite Monoids: From Word to Circuit Evaluation
cites work: Computing Algebraic Formulas Using a Constant Number of Registers
cites work: The Theory of Stabilisation Monoids and Regular Cost Functions
cites work: Regular cost functions. I: Logic and algebra over words
cites work: Q4601881
cites work: A Generalised Twinning Property for Minimisation of Cost Register Automata
cites work: Handbook of weighted automata
cites work: Q4843270
cites work: Uniform constant-depth threshold circuits for division and iterated multiplication.
cites work: The iterated mod problem
cites work: Cost Register Automata for Nested Words
cites work: Straight-line program length as a parameter for complexity analysis
cites work: Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties
cites work: Q4395212
cites work: Q4302435
cites work: Q4393484
full work available at URL: lipics.mfcs.2017.24
OpenAlex ID: W2940923581
title: Better complexity bounds for cost register automata
DOI: 10.4230/LIPICS.MFCS.2017.24
description: scientific article; zbMATH DE number 7204358