Result Details
Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete
        KŘIVKA, Z.; MEDUNA, A. Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete. FUNDAMENTA INFORMATICAE, 2021, vol. 179, no. 4, p. 361-384.  ISSN: 0169-2968.
    
                Type
            
        
                journal article
            
        
                Language
            
        
                English
            
        
            Authors
            
        
                    Abstract
            
        This paper investigates the reduction of scattered context grammars with respect to the number of non-context-free productions. It proves that every recursively enumerable language is generated by a scattered context grammar that has no more than one non-context-free production. An open problem is formulated.
                Keywords
            
        Scattered context grammars, size reduction, the number of non-context-free productions, parallel productions, computational completeness, descriptional complexity
                Published
            
            
                    2021
                    
                
            
                    Pages
                
            
                        361–384
                
            
                    Journal
                
            
                    FUNDAMENTA INFORMATICAE, vol. 179, no. 4, ISSN 0169-2968
                
            
                    DOI
                
            
                    UT WoS
                
            
                    000651794800003
                
            
                EID Scopus
                
            
                    BibTeX
                
            @article{BUT162265,
  author="Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete",
  journal="FUNDAMENTA INFORMATICAE",
  year="2021",
  volume="179",
  number="4",
  pages="361--384",
  doi="10.3233/FI-2021-2028",
  issn="0169-2968",
  url="https://www.fit.vut.cz/research/publication/11559/"
}
                Files
            
        
                Projects
            
        
        
            
        
    
    
        Efficient Finite Automata for Automated Reasoning, MŠMT, ERC CZ, LL1908, start: 2020-01-01, end: 2024-12-31, completed
                
IT4Innovations excellence in science, MŠMT, Národní program udržitelnosti II, LQ1602, start: 2016-01-01, end: 2020-12-31, completed
        IT4Innovations excellence in science, MŠMT, Národní program udržitelnosti II, LQ1602, start: 2016-01-01, end: 2020-12-31, completed
                Research groups
            
        
                Formal Model Research Group (RG FM)
            
        
                Departments