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

Boolean Grammars Are Closed Under Inverse Gsm Mappings

Tommi Lehtinen, Alexander Okhotin, Boolean Grammars Are Closed Under Inverse Gsm Mappings. TUCS Technical Reports 911, Turku Centre for Computer Science, 2008.

Abstract:

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

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tLeOk08a,
  title = {Boolean Grammars Are Closed Under Inverse Gsm Mappings},
  author = {Lehtinen, Tommi and Okhotin, Alexander},
  number = {911},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2008},
  keywords = {Boolean grammars, conjunctive grammars, closure properties, gsm mappings},
  ISBN = {978-952-12-2147-7},
}

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

Edit publication