The focus of this book is a mathematical structure modeling a physical or biological system that can be in any of a number of `states.' Each state is characterized by a set of binary features, and differs from some other neighbor state or states by just one of those feature. A simple example of a `state’ is a partial solution of a jigsaw puzzle, which can be transformed into another partial solution or into the final solution just by adding or removing a single adjoining piece. The evolution of such a system over time is considered. Such a structure is analyzed from algebraic and probabilistic (stochastic) standpoints.
Author(s): David Eppstein, Jean-Claude Falmagne, Sergei Ovchinnikov (auth.)
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2008
Language: English
Pages: 328
Tags: Applications of Mathematics; Theory of Computation; Artificial Intelligence (incl. Robotics); Combinatorics
Front Matter....Pages I-X
Examples and Preliminaries....Pages 1-21
Basic Concepts....Pages 23-47
Media and Well-graded Families....Pages 49-71
Closed Media and ∪-Closed Families....Pages 73-99
Well-Graded Families of Relations....Pages 101-121
Mediatic Graphs....Pages 123-137
Media and Partial Cubes....Pages 139-160
Media and Integer Lattices....Pages 161-175
Hyperplane arrangements and their media....Pages 177-198
Algorithms....Pages 199-228
Visualization of Media....Pages 229-262
Random Walks on Media....Pages 263-284
Applications....Pages 285-303
Back Matter....Pages 305-328
