Complexity of regular functions

DOI10.1016/j.jcss.2016.10.005zbMath1435.68139OpenAlexW2547724419MaRDI QIDQ2424670

Eric W. Allender, Ian Mertz

Publication date: 25 June 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2016.10.005

zbMATH Keywords

computational complexitytransducersweighted automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Special issue: Selected papers of the 9th international conference on language and automata theory and applications, LATA 2015

Cites Work

• Unnamed Item
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Nondeterministic \(NC^1\) computation
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Complexity of Regular Functions
• Cost Register Automata for Nested Words
• Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
• Expressiveness of Streaming String Transducers
• Computing Algebraic Formulas Using a Constant Number of Registers
• An Optimal Parallel Algorithm for Formula Evaluation
• MSO definable string transductions and two-way finite-state transducers
• Regular combinators for string transformations
• On the Complexity of Equivalence and Minimisation for Q-weighted Automata
• Regular Functions and Cost Register Automata
• 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
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs