Author name cluster

D. Simplot

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

TCS Journal 2000 Journal Article

Undecidability of existential properties in picture languages

D. Robilliard
D. Simplot

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 [10]. 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”.

Details DOI

I&C Journal 1997 Journal Article

Context-Sensitive String Languages and Recognizable Picture Languages

M. Latteux
D. Simplot

The theorem stating that the family of frontiers of recognizable tree languages is exactly the family of context-free languages (see J. Mezei and J. B. Wright, 1967, Inform. and Comput. 11, 3–29), is a basic result in the theory of formal languages. In this article, we prove a similar result: the family of frontiers of recognizable picture languages is exactly the family of context-sensitive languages

Details DOI