The STUDIA UNIVERSITATIS BABEŞ-BOLYAI issue article summary

The summary of the selected article appears at the bottom of the page. In order to get back to the contents of the issue this article belongs to you have to access the link from the title. In order to see all the articles of the archive which have as author/co-author one of the authors mentioned below, you have to access the link from the author's name.

  
       
         
    STUDIA INFORMATICA - Issue no. 1 / 2006  
         
  Article:   PREFIX-FREE LANGUAGES, SIMPLE GRAMMARS REPRESENTING A GROUP ELEMENT, LANGUAGES OF PARTIAL ORDER IN A GROUP.

Authors:  KRASSIMIR D. TARKALANOV. 		 
       
         
  Abstract:  We show each word in the Kleene closure of a prefix-free language over an arbitrary alphabet has only one presentation as a concatenation of its words. It follows this language is the largest prefix-free one in the closure and both of them are simultaneously recursive or not recursive. We note if a complete simple grammar generates words only from a prefix-free language, the generated language exhausts it entirely. Such particular results only for word- and reduced word problem languages of a group can be found in [1, 4]. Using appropriate parts of the repeated in [4] construction from [1] we construct entire simple grammars whose terminal set is the monoid generating set of a group. The start symbol can be indexed by any element of the group and then the corresponding grammar will generate only representatives of this element. If all of them contain in its prefix-free part, their set exhausts this part according to the note above. Following [4] the reduced word problem language must be a such part of the word problem language for a group with finite irreducible word problem and the simple grammar there. The answer to the final question 5.3. [4] is absolutely analogous and simply follows the proof from [1]. We give necessary and suficient conditions which a language must satisfy together with these [4] for a word problem language in order the first one to assign a partial order in the group of the second one.  
         
     
         
         
      Back to previous page