Formal Grammars
A Journal of Mathematical Research on Formal and Natural Languages

Editor-in-chief: Carlos Martín-Vide
Special issues
Introduction
Volume 7(2004)
Volume 8(2005)
Editorial board
Aims and Scope
Subscription to the Hardcopy Edition
Submission procedure


Using Alternating Words to Describe Symbolic Pictures

GENNARO COSTAGLIOLA, FILOMENA FERRUCCI, RITA FRANCESE, CARMINE GRAVINO
Department of Mathematics and Computer Science, Universitá di Salerno, Italy
84081 Baronissi (SA), Italy
e-mail:{gcostagliola, fferrucci, francese, gravino}@unisa.it

Abstract

In this paper we present the concepts of drawn symbolic picture and symbolic picture. Such notions have been conceived as an extension of the concept of drawn pictures which was introduced by Maurer, Rozenberg and Welzl [31]. We provide a string description of such pictures. It consists of alternating words, i.e. strings whose letters are in alternation from an alphabet of symbols and an alphabet of moves. We analyze the complexity of the description language of a (drawn) symbolic picture and show how these yield context-sensitive, context-free and regular languages. Then, we characterize the grammars for alternating words and define the generative model for (drawn) symbolic pictures. Moreover, we investigate the different types of ambiguity that occur when dealing with symbolic grammars. Finally, we propose a classification for symbolic picture grammars and languages.

Download:
PS file
PDF file
Copyright © 2004 GRLMC. All rights reserved.
Research Group on Mathematical Linguistics - Rovira i Virgili University
Webmaster