New Findings on Computer Science Research Described by Inves
Source: Elsevier
Data detailed on Computer Science Research have been presented. According to news reporting originating from Ithaca, New York, by VerticalNews correspondents, research stated, "We explore the capability of a network of extremely limited computational entities to decide properties about itself or any of its subnetworks. We consider that the underlying network of the interacting entities (devices, agents, processes etc.) is modeled by an interaction graph that reflects the network's connectivity."
We obtained a quote from the research from Cornell University, "We examine the following two cases: First, we consider the case where the input graph is the whole interaction graph and second where it is some subgraph of the interaction graph given by some preprocessing on the network. In each case, we devise simple graph protocols that can decide properties of the input graph. The computational entities, that are called agents, are modeled as finite-state automata and run the same global graph protocol. Each protocol is a fixed size grammar, that is, its description is independent of the size (number of agents) of the network. This size is not known by the agents. We present two simple models (one for each case), the Graph Decision Mediated Population Protocol (GDMPP) and the Mediated Graph Protocol (MGP) models, similar to the Population Protocol model of Angluin et al., where each network link (edge of the interaction graph) is characterized by a state taken from a finite set. This state can be used and updated during each interaction between the corresponding agents. We provide some example protocols and some interesting properties for the two models concerning the computability of graph languages in various settings (disconnected input graphs, stabilizing input graphs). We show that the computational power within the family of all (at least) weakly-connected input graphs is fairly restricted."
According to the news editors, the research concluded: "Finally, we give an exact characterization of the class of graph languages decidable by the MGP model in the case of complete interaction graphs: it is equal to the class of graph languages decidable by a nondeterministic Turing Machine of linear space that receives its input graph by its adjacency matrix representation."
For more information on this research see: The computational power of simple protocols for self-awareness on graphs. Theoretical Computer Science, 2013;512():98-118. Theoretical Computer Science can be contacted at: Elsevier Science Bv, PO Box 211, 1000 Ae Amsterdam, Netherlands. (Elsevier - www.elsevier.com; Theoretical Computer Science - www.elsevier.com/wps/product/cws_home/505625)
The news editors report that additional information may be obtained by contacting I. Chatzigiannakis, Cornell University, Dept. of Comp Sci, Ithaca, NY 14853, United States. Additional authors for this research include O. Michail, S. Nikolaou and P.G. Spirakis.
Keywords for this news article include: Ithaca, New York, United States, North and Central America, Computer Science Research
Our reports deliver fact-based news of research and discoveries from around the world.
| }
|