Language complexity on the synchronous anonymous ring

DOI10.1016/0304-3975(87)90062-4zbMath0643.68120OpenAlexW2088281739MaRDI QIDQ1102125

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

gap theoremcomputable functioncounter-free regular languagesdistributed networks of processorssynchronous anonymous ring

Mathematics Subject Classification ID

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

Related Items (2)

Hundreds of impossibility results for distributed computing ⋮ Anonymous wireless rings

Cites Work

• Lower Bounds for Distributed Maximum-Finding Algorithms
• Computing on an anonymous ring
• 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
• Unnamed Item
• Unnamed Item

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