Result Details
Random Context and Programmed Grammars of Finite Index Have The Same Generative Power
        KŘIVKA, Z.; MEDUNA, A. Random Context and Programmed Grammars of Finite Index Have The Same Generative Power. Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling. 1st edition. Ostrava: Marq software s.r.o., 2005. p. 67-72.  ISBN: 80-86840-09-3.
    
                Type
            
        
                conference paper
            
        
                Language
            
        
                English
            
        
            Authors
            
        
                    Abstract
            
        The question of whether for every programmed grammar of index k, there is an equivalent a random context grammar in which every production has no forbidding context represents an open problem in the formal language theory. This paper solves this problem by establishing this equivalence.
                Keywords
            
        random context grammars, permitting grammars, programmed grammars, finite index, generative power
                    Annotation
                
            The question of whether for every programmed grammar of index k, there is an equivalent a random context grammar in which every production has no forbidding context represents an open problem in the formal language theory. This paper solves this problem by establishing this equivalence.
                Published
            
            
                    2005
                    
                
            
                    Pages
                
            
                        67–72
                
            
                        Proceedings
                
            
                    Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling
                
            
                    Series
                
            
                    1st edition
                
            
                    Conference
                
            
                    8th International Conference on Information Systems Implementation and Modelling
                
            
                    ISBN
                
            
                    80-86840-09-3
                
            
                    Publisher
                
            
                    Marq software s.r.o.
                
            
                    Place
                
            
                    Ostrava
                
            
                    BibTeX
                
            @inproceedings{BUT21455,
  author="Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Random Context and Programmed Grammars of Finite Index Have The Same Generative Power",
  booktitle="Proceedings of 8th International Conference ISIM'05 Information Systems Implementation and Modelling",
  year="2005",
  series="1st edition",
  pages="67--72",
  publisher="Marq software s.r.o.",
  address="Ostrava",
  isbn="80-86840-09-3"
}
                Projects
            
        
        
            
        
    
    
        Optimally Integrated Models of Modern Information Technologies, GACR, Standardní projekty, GA201/04/0441, start: 2004-01-01, end: 2006-12-31, completed
            
        
                Research groups
            
        
                Formal Model Research Group (RG FM)
            
        
                Departments