Kaya Deuser

Kaya Deuser, Pavel Naumov

The article studies navigability of an autonomous agent in a maze where some rooms may be indistinguishable. In a previous work the authors have shown that the properties of navigability in such a setting depend on whether an agent has perfect recall. Navigability by an agent with perfect recall is a transitive relation and without is not transitive. This article introduces a notion of restricted navigability and shows that a certain form of transitivity holds for restricted navigability, even for an agent without perfect recall. The main technical result is a sound and complete logical system describing the properties of restricted navigability.

Kaya Deuser, Pavel Naumov

The paper investigates navigability with imperfect information. It shows that the properties of navigability with perfect recall are exactly those captured by Armstrong's axioms from the database theory. If the assumption of perfect recall is omitted, then Armstrong's transitivity axiom is not valid, but it can be replaced by two new weaker principles. The main technical results are soundness and completeness theorems for the logical systems describing properties of navigability with and without perfect recall.