Asynchronous and Synchronous Parallel Derivation of Formal Languages

Katsuhiko NAKAMURA

Asynchronous and Synchronous Parallel Derivation of Formal Languages

Katsuhiko NAKAMURA

Full Text Views

0

Cite this

Summary :

This paper discusses the asynchronous and synchronous parallel derivation of languages based on standard formal grammars. Some of the synchronous languages defined in this paper are essentially equivalent to the languages of E0L and EIL systems. Languages with restrictions on the number of parallel derivation steps are difined so that a t-time language is the set of strings w derived in t(w) or less parallel derivatio steps, where t(n) is an integer function. the properties of asynchronous derivation are generally discussed to clarify their conditions so that the derivation results are independent of the order in which productions are applied. It is shown that: (1) Any context sensitive grammar (CSG) G can be transformed into a CSG G such that the language generated by synchronous derivation in G is equal to that generated by asynchronous derivation in G , and vice versa; (2) Any regular language is a log-time context free language (CFL); (3) The class of CFLs is incomparable with that of log-time CSLs; and (4) If there is a bounded cellular automaton recognizing any language L in time T(n), then L is an O(T(n))-time CSL.

Publication: IEICE TRANSACTIONS on Information Vol.E77-D No.5 pp.539-545

Publication Date: 1994/05/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Automata, Languages and Theory of Computing

Cite this

Copy

Katsuhiko NAKAMURA, "Asynchronous and Synchronous Parallel Derivation of Formal Languages" in IEICE TRANSACTIONS on Information, vol. E77-D, no. 5, pp. 539-545, May 1994, doi: .
Abstract: This paper discusses the asynchronous and synchronous parallel derivation of languages based on standard formal grammars. Some of the synchronous languages defined in this paper are essentially equivalent to the languages of E0L and EIL systems. Languages with restrictions on the number of parallel derivation steps are difined so that a t-time language is the set of strings w derived in t(w) or less parallel derivatio steps, where t(n) is an integer function. the properties of asynchronous derivation are generally discussed to clarify their conditions so that the derivation results are independent of the order in which productions are applied. It is shown that: (1) Any context sensitive grammar (CSG) G can be transformed into a CSG G such that the language generated by synchronous derivation in G is equal to that generated by asynchronous derivation in G , and vice versa; (2) Any regular language is a log-time context free language (CFL); (3) The class of CFLs is incomparable with that of log-time CSLs; and (4) If there is a bounded cellular automaton recognizing any language L in time T(n), then L is an O(T(n))-time CSL.
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_5_539/_p

Copy

@ARTICLE{e77-d_5_539,
author={Katsuhiko NAKAMURA, },
journal={IEICE TRANSACTIONS on Information},
title={Asynchronous and Synchronous Parallel Derivation of Formal Languages},
year={1994},
volume={E77-D},
number={5},
pages={539-545},
abstract={This paper discusses the asynchronous and synchronous parallel derivation of languages based on standard formal grammars. Some of the synchronous languages defined in this paper are essentially equivalent to the languages of E0L and EIL systems. Languages with restrictions on the number of parallel derivation steps are difined so that a t-time language is the set of strings w derived in t(w) or less parallel derivatio steps, where t(n) is an integer function. the properties of asynchronous derivation are generally discussed to clarify their conditions so that the derivation results are independent of the order in which productions are applied. It is shown that: (1) Any context sensitive grammar (CSG) G can be transformed into a CSG G such that the language generated by synchronous derivation in G is equal to that generated by asynchronous derivation in G , and vice versa; (2) Any regular language is a log-time context free language (CFL); (3) The class of CFLs is incomparable with that of log-time CSLs; and (4) If there is a bounded cellular automaton recognizing any language L in time T(n), then L is an O(T(n))-time CSL.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Asynchronous and Synchronous Parallel Derivation of Formal Languages
T2 - IEICE TRANSACTIONS on Information
SP - 539
EP - 545
AU - Katsuhiko NAKAMURA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 1994
AB - This paper discusses the asynchronous and synchronous parallel derivation of languages based on standard formal grammars. Some of the synchronous languages defined in this paper are essentially equivalent to the languages of E0L and EIL systems. Languages with restrictions on the number of parallel derivation steps are difined so that a t-time language is the set of strings w derived in t(w) or less parallel derivatio steps, where t(n) is an integer function. the properties of asynchronous derivation are generally discussed to clarify their conditions so that the derivation results are independent of the order in which productions are applied. It is shown that: (1) Any context sensitive grammar (CSG) G can be transformed into a CSG G such that the language generated by synchronous derivation in G is equal to that generated by asynchronous derivation in G , and vice versa; (2) Any regular language is a log-time context free language (CFL); (3) The class of CFLs is incomparable with that of log-time CSLs; and (4) If there is a bounded cellular automaton recognizing any language L in time T(n), then L is an O(T(n))-time CSL.
ER -