Adapting to the Behavior of Environments with Bounded Memory
| Autor: | Dhananjay Raju, Rüdiger Ehlers, Ufuk Topcu |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Theoretical computer science Computer science Formal Languages and Automata Theory (cs.FL) B.1.2 D.2.3 Control (management) Computer Science - Formal Languages and Automata Theory Scale (descriptive set theory) Upper and lower bounds Turing machine symbols.namesake Computer Science - Computer Science and Game Theory Control theory Bounded function symbols Temporal logic PSPACE Computer Science and Game Theory (cs.GT) |
| DOI: | 10.48550/arxiv.2109.08316 |
| Popis: | We study the problem of synthesizing implementations from temporal logic specifications that need to work correctly in all environments that can be represented as transducers with a limited number of states. This problem was originally defined and studied by Kupferman, Lustig, Vardi, and Yannakakis. They provide NP and 2-EXPTIME lower and upper bounds (respectively) for the complexity of this problem, in the size of the transducer. We tighten the gap by providing a PSPACE lower bound, thereby showing that algorithms for solving this problem are unlikely to scale to large environment sizes. This result is somewhat unfortunate as solving this problem enables tackling some high-level control problems in which an agent has to infer the environment behavior from observations. To address this observation, we study a modified synthesis problem in which the synthesized controller must gather information about the environment's behavior safely. We show that the problem of determining whether the behavior of such an environment can be safely learned is only co-NP-complete. Furthermore, in such scenarios, the behavior of the environment can be learned using a Turing machine that requires at most polynomial space in the size of the environment's transducer. Comment: In Proceedings GandALF 2021, arXiv:2109.07798 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|