|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc020103,
author = {Ferucio Lauren\c{t}iu \c{T}iplea and
Masashi Katsura and Masami Ito},
title = {Processes and Vectorial Characterizations of
Parallel Communicating Grammar Systems},
journal = jalc,
year = 1997,
volume = 2,
number = 1,
pages = {47--73},
keywords = {grammar and system of grammars, Petri net, process, partial word
and language},
abstract = {This paper deals with regular Parallel Communicating
Grammar Systems (PCGS, for short), and basically it has two
main parts. The first one introduces and studies
processes and partial words of PCGS, while the second one
gives some vectorial characterizations of sequential
languages of PCGS.\par
Processes and partial words of PCGS are defined using
conflict occurrence nets, and they intend to capture
concurrent behaviours, including communications, of such
systems of grammars. From processes, partial words and
communication partial words are derived. We show that
processes and partial words of PCGS are Petri net generable,
and some consequences are then obtained. The connection with
regular partial languages is also made. Namely, we show that
partial languages of conflict-free unsynchronized PCGS are
regular partial languages. The vectorial characterizations
that we present here are based on special catenations on
vectors of strings, and vectorial languages. More precisely,
we show that languages generated by PCGS are images of
regular languages through special kinds of
``substitutions'' and ``homomorphisms''.
Each section points out some open problems and possible
directions for a further study.}
}