Language complexity on the synchronous anonymous ring

DOI10.1016/0304-3975(87)90062-4MaRDI QIDQ1102125zbMATH OpenOpenAlexFDO

Authors Hagit Attiya, Yishay Mansour

Publication date 1987

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(87)90062-4

zbMATH Keywords

computable functioncounter-free regular languagesdistributed networks of processorsgap theoremsynchronous anonymous ring

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Theory of software (68N99) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Computing on an anonymous ring
• On the bit complexity of distributed computations in a ring with a leader
• Better computing on the anonymous ring
• On recognizing a string on an anonymous ring
• Gap Theorems for Distributed Computation

Cites work

• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Computing on an anonymous ring
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Lower Bounds for Distributed Maximum-Finding Algorithms

Cited in

(9)

• String recognition on anonymous rings
• Computing on an anonymous ring
• scientific article; zbMATH DE number 17531 (Why is no real title available?)
• scientific article; zbMATH DE number 1754655 (Why is no real title available?)
• Hundreds of impossibility results for distributed computing
• scientific article; zbMATH DE number 5201364 (Why is no real title available?)
• On recognizing a string on an anonymous ring
• Anonymous wireless rings
• Scattering on a ring of processors

This page was built for publication: Language complexity on the synchronous anonymous ring

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