• 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 homomorphisms

Tommi Lehtinen, Alexander Okhotin, Boolean grammars are closed under inverse homomorphisms. TUCS Technical Reports 846, Turku Centre for Computer Science, 2007.

Abstract:

It is proved that for every Boolean grammar <i>G</i> and for every homomorphism <i>h</i>, the set <i>h</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{tLeOk07a,
  title = {Boolean grammars are closed under inverse homomorphisms},
  author = {Lehtinen, Tommi and Okhotin, Alexander},
  number = {846},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2007},
  keywords = {Boolean grammars, conjunctive grammars, closure properties, homomorphism},
  ISBN = {978-952-12-1965-8},
}

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

Edit publication