Feature logics are the logical basis for so-called unification grammars studied in computational linguistics. We investigate the expressivity of feature terms with negation and the functional uncertainty construct needed for the description of long-distance dependencies and obtain the following results: satisfiability of feature terms is undecidable, sort equations can be internalized, consistency of sort equations is decidable if there is at least one atom, and consistency of sort equations is undecidable if there is no atom.

Alan Turing, einer der Gründerväter der modernen Informatik, diskutierte in seinem 1950 veröffentlichten Artikel »Computing Machinery and Intelligence« die Frage, ob Maschinen denken können. Dies wirft jedoch die schwierige Frage auf, was Denken denn sei. Um diese Frage zu umgehen, schlägt Turing vor, stattdessen eine Frage zu stellen, die sich durch bloße Beobachtung klären lässt, nämlich ob eine Maschine ein bestimmtes Spiel erfolgreich spielen könne.

The generation of route descriptions is a fundamental task of navigation systems. A particular problem in this context is to identify routes that can easily be described and processed by users. In this work, we present a framework for representing route networks with the qualitative information necessary to evaluate and optimize route descriptions with regard to ambiguities in them. We identify different agent models that differ in how agents are assumed to process route descriptions while navigating through route networks and (...) discuss which agent models can be translated into PDL programs. Further, we analyze the computational complexity of matching route descriptions and paths in route networks in dependency of the agent model. Finally, we empirically evaluate the influence of the agent model on the optimization and the processing of route instructions. (shrink)