Words are used to model computational phenomena like linear sequences of events or signals, runs of a deterministic program, etc.Anatural generalisation of aword is a tree. Not only do trees play a significant role in computer science as data structures, for instance in binary search trees, they also naturally generalise the model of a sequence of events with a designated starting point and a unique successor at each moment, to a model of runs of nondeterministic programs for instance: instead of a unique next moment there may be several possible next moments. Reasoning about the entirety of the behaviour of such a program – instead of all its single runs only – then requires it to be viewed as a tree.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Automata on Finite Trees

  • Martin Hofmann,
  • Martin Lange

摘要

Words are used to model computational phenomena like linear sequences of events or signals, runs of a deterministic program, etc.Anatural generalisation of aword is a tree. Not only do trees play a significant role in computer science as data structures, for instance in binary search trees, they also naturally generalise the model of a sequence of events with a designated starting point and a unique successor at each moment, to a model of runs of nondeterministic programs for instance: instead of a unique next moment there may be several possible next moments. Reasoning about the entirety of the behaviour of such a program – instead of all its single runs only – then requires it to be viewed as a tree.