• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Boolean grammars and gsm mappings

Tommi Lehtinen, Alexander Okhotin, Boolean grammars and gsm mappings. In: Automat and Formal Languages. The 12th International Conference, AFL 2008, Balatonfüred, Hungary, May 27-30, 2008, Proceedings., 2008.

Abstract:

It is proved that for every Boolean grammar $G$
and for every generalized sequential machine $M$,
the set $M^{-1}(L(G))$ of pre-images
of words generated by $G$
is generated by a Boolean grammar,
which can be effectively constructed.
Furthermore, if $G$ is unambiguous,
the constructed grammar is unambiguous as well.
These results extend to conjunctive grammars.

BibTeX entry:

@INPROCEEDINGS{inpLeOk08a,
  title = {Boolean grammars and gsm mappings},
  booktitle = {Automat and Formal Languages. The 12th International Conference, AFL 2008, Balatonfüred, Hungary, May 27-30, 2008, Proceedings.},
  author = {Lehtinen, Tommi and Okhotin, Alexander},
  year = {2008},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication