BOOLEAN GRAMMARS AND GSM MAPPINGS

: Lehtinen Tommi, Okhotin Alexander

Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD

: 2010

: International Journal of Foundations of Computer Science

: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

: INT J FOUND COMPUT S

: 5

: 21

: 5

: 799

: 815

: 17

: 0129-0541

DOI: https://doi.org/10.1142/S0129054110007568

It is proved that the language family generated by Boolean grammars is effectively closed under injective gsm mappings and inverse gsm mappings (where gsm stands for a generalized sequential machine).The same results hold for conjunctive grammars, unambiguous Boolean grammars and unambiguous conjunctive grammars