Parallel complexity of iterated morphisms and the arithmetic of small numbers

DOI10.1007/3-540-55808-X_21MaRDI QIDQ5096834zbMATH OpenFDO

Authors Carsten Damm, Markus Holzer, Klaus-Jörn Lange

Publication date 18 August 2022

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

Full work available at URL https://doi.org/10.1007/3-540-55808-X_21

Mathematics Subject Classification ID

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

Recommendations

• On periodically iterated morphisms
• scientific article; zbMATH DE number 1722707
• On the computational complexity of infinite words.
• scientific article; zbMATH DE number 1834659
• A new bound for the D0L sequence equivalence problem

Cites work

• A Note on the Complexity of General D0L Membership
• A taxonomy of problems with fast parallel algorithms
• Complexity of some problems concerningL systems
• Constant Depth Reducibility
• scientific article; zbMATH DE number 4047100 (Why is no real title available?)
• scientific article; zbMATH DE number 4079403 (Why is no real title available?)
• scientific article; zbMATH DE number 45125 (Why is no real title available?)
• scientific article; zbMATH DE number 3459900 (Why is no real title available?)
• scientific article; zbMATH DE number 3557232 (Why is no real title available?)
• scientific article; zbMATH DE number 3802813 (Why is no real title available?)
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Recognition of deterministic ETOL languages in logarithmic space
• The membership question for ETOL-languages is polynomially complete
• Threshold circuits of bounded depth

Cited in

(5)

• On the computational complexity of infinite words.
• Small deviations, JIT sequencing and symmetric case of Fraenkel's conjecture
• scientific article; zbMATH DE number 1722707 (Why is no real title available?)
• Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)
• Descriptional and computational complexity of finite automata -- a survey

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096834)