Foundations of Linguistic Geometry: Complex Systems and Winning Strategies
Vladimir Yakhnis · 1996
The Linguistic Geometry (LG) approach to discrete systems was introduced B. Stilman in early 80s. It employed competing/cooperating agents for modeling and controlling of discrete systems. The approach was applied to a variety of problems with huge state spaces including control of aircraft, battlefield robots, and chess. One of the key innovations of LG is the use of almost winning strategies, rather than truly winning strategies for the playing agents. There are many cases where the winning strategies have so high time complexity that they are not computable in practice, whereas the almost winning strategies can be applied and they beat the opposing agent almost guaranteed. Independently of LG the idea of competing/ cooperating agents was employed in the late 80s by A. Nerode, A. Yakhnis, and V. Yakhnis (NYY) within their approach to modeling concurrent systems and, more recently, within the “Strategy Approach to Hybrid Systems ” developed for continuous systems by A. Nerode, W. Kohn, A. Yakhnis, and others. In order to enlarge the range of applications of Stilman's results as well as to understand why they work, we introduce a new notion of a multi-agent graph-game. Since the applications of Linguistic Geometry sometimes require modeling of agents making simultaneous moves, the new notion was designed to accommodate such behavior of players.