𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Undecidability of existential properties in picture languages

✍ Scribed by D. Robilliard; D. Simplot

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
789 KB
Volume
233
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We are interested in the description of a set of pictures by string languages by using several semantics: segments [12], segments with blank moves [8] and pixels . We give a method to code the Post correspondence problem in rational picture languages in order to show the undecidability of existence of words satisfying a given property in a rational language. In particular, we study the properties like "is a self-avoiding word", "is a minimal picture word" or "describes a connected picture".

πŸ“œ SIMILAR VOLUMES

The complexity of existential quantifica
The complexity of existential quantification in concept languages
✍ Francesco M. Donini; Maurizio Lenzerini; Daniele Nardi; Bernhard Hollunder; Wern πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 965 KB

Much of the research on concept languages, which also are called terminological languages, has focused on the computational complexity of subsumption. The intractability results can be divided into two groups. First, it has been shown that extending the basic language ,~Sfwith constructs containing