Geodesic
A Constructive Proof of Equivalence of Formalism od DCG's With the Formalism of Type 0 Phrase-structure Grammars
Publications de l'Institut Mathématique, _N_S_56 (1994) no. 70, p. 7 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

We present a proof that definite clause grammars (DCG's) are equivalent in their generative power to type 0 phrase-structure grammars. The proof is constructive and it actually describes an algorithm for transferring from a language description by type 0 grammar to DCG characterization. The proof has been inspired by the proof given in [MA93] but our approach is considerably simpler and the constructed DCG grammar is much more efficient. The paper also suggests how computer implementation of the algorithm can be developed.
Classification : 03B65 
@article{PIM_1994_N_S_56_70_a1,
     author = {Marica D. Pre\v{s}i\'c and Slavi\v{s}a B. Pre\v{s}i\'c},
     title = {A {Constructive} {Proof} of {Equivalence} of {Formalism} od {DCG's} {With} the {Formalism} of {Type} 0 {Phrase-structure} {Grammars}},
     journal = {Publications de l'Institut Math\'ematique},
     pages = {7 },
     publisher = {mathdoc},
     volume = {_N_S_56},
     number = {70},
     year = {1994},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PIM_1994_N_S_56_70_a1/}
}
TY  - JOUR
AU  - Marica D. Prešić
AU  - Slaviša B. Prešić
TI  - A Constructive Proof of Equivalence of Formalism od DCG's With the Formalism of Type 0 Phrase-structure Grammars
JO  - Publications de l'Institut Mathématique
PY  - 1994
SP  - 7 
VL  - _N_S_56
IS  - 70
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PIM_1994_N_S_56_70_a1/
LA  - en
ID  - PIM_1994_N_S_56_70_a1
ER  - 
%0 Journal Article
%A Marica D. Prešić
%A Slaviša B. Prešić
%T A Constructive Proof of Equivalence of Formalism od DCG's With the Formalism of Type 0 Phrase-structure Grammars
%J Publications de l'Institut Mathématique
%D 1994
%P 7 
%V _N_S_56
%N 70
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PIM_1994_N_S_56_70_a1/
%G en
%F PIM_1994_N_S_56_70_a1
Marica D. Prešić; Slaviša B. Prešić. A Constructive Proof of Equivalence of Formalism od DCG's With the Formalism of Type 0 Phrase-structure Grammars. Publications de l'Institut Mathématique, _N_S_56 (1994) no. 70, p. 7 . http://geodesic.mathdoc.fr/item/PIM_1994_N_S_56_70_a1/