Parallel complexity of iterated morphisms and the arithmetic of small numbers

DOI10.1007/3-540-55808-X_21zbMath1493.68186MaRDI QIDQ5096834

Markus Holzer, Carsten Damm, Klaus-Joern Lange

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (1)

Descriptional and computational complexity of finite automata -- a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On uniform circuit complexity
• The membership question for ETOL-languages is polynomially complete
• Threshold circuits of bounded depth
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Constant Depth Reducibility
• A taxonomy of problems with fast parallel algorithms
• Complexity of some problems concerningL systems
• A Note on the Complexity of General $D0L$ Membership
• Recognition of deterministic ETOL languages in logarithmic space

This page was built for publication: Parallel complexity of iterated morphisms and the arithmetic of small numbers