COUNTEREXAMPLES AND BOUNDS FOR GRAPHS SOLVABLE WITH FINITE DELAY,

Abstract

A finite directed labelled graph G with vertices v sub i, i=1 to i=n and labels (sigma sub i) subscript (sigma sub i epsilon Sigma) is solvable with delay d if for every sequence of labels sigma sub 1,..., sigma sub k one can determine a sequence of vertices v sub (i sub 0)---v sub (i sub k) such that there is a path connecting the vertices v sub (i sub 0)---v sub (i sub k), labeled sigma sub 1 --- sigma sub k and for every j v sub ij is determined by the subsequence sigma sub (j+1) --- sigma sub (j+d) only. The paper presents a family of counterexamples proving a new lower bound for d. A new simple proof is given for a known upper bound for d and a new upper bound for d is given for the case where the sequences of labels are restricted to a regular event.

Document Details

Document Type
Technical Report
Publication Date
Oct 03, 1969
Accession Number
AD0695034

Entities

People

  • A. Paz

Organizations

  • University of California, Los Angeles

Tags

DTIC Thesaurus Topics

  • Behavior And Behavior Mechanisms
  • Behavioral Disciplines And Activities
  • Behavioral Sciences
  • Cooperation
  • Families (Human)
  • Group Dynamics
  • Mathematics
  • Sequences

Readers

  • Analytical Mechanics
  • Mathematical Modeling and Probability Theory.
  • Neural Network Machine Learning.