Church-Rosser groups and growing context-sensitive groups

A finitely generated group is called a Church-Rosser group (growing context-sensitive group) if it admits a finitely generated presentation for which the word problem is a Church-Rosser (growing context-sensitive) language. Although the Church-Rosser languages are incomparable to the context-free languages under set inclusion, they strictly contain the class of deterministic context-free languages. As each context-free group language is actually deterministic context-free, it follows that all context-free groups are Church-Rosser groups. As the free abelian group of rank 2 is a non-context-free Church-Rosser group, this inclusion is proper. On the other hand, we show that there are co-context-free groups that are not growing context-sensitive. Also some closure and non-closure properties are established for the classes of Church-Rosser and growing context-sensitive groups. More generally, we also establish some new characterizations and closure properties for the classes of Church-Rosser and growing context-sensitive languages.

The Corticiaceae (Basidiomycetes) in Taiwan

Geographically, Taiwan is an Island and situated in the northeast of Asia, on the western side of the Pacific Basin, at the southeast of main China, south of Japan, and north of the Philippines. The main topographic character is the longitudinally oriented mountainous area. More than 200 peaks rise above 3000 m. They departed Taiwan into two lowland areas, an eastern and western plain. Taiwan is departed into subtropical (north area) and tropical zone (south area), which have a warm and humid climate, due to the Tropic of Cancer passing through. The average annual temperature in the lowland amounts to 28°C (7~38°C). The temperate climate also presents in the mountainous areas. The tropical typhoons usually come in summer and bring heavy rain, while the monsoon seasons have an important effect on the regional rainfall distribution. The mean annual rainfall of Taiwan is about 2600 mm (1000~6700 mm); the mountainous areas receive more rain than the lowlands. In Taiwan, according to different temperature and vegetation, the ecological environments were given rise to vertical biotic zonations, and form five major types: highland snowfield, highland meadow, coniferous forest, deciduous forest, and tropical forest. Six National Parks in Taiwan are located in the mountainous areas, in the north, the south, and on Jinmen Island. The National Parks represent about 8.4% of the country area. In this study, the collection sites are situated in Yangmingshan, Shei-Pa, Yushan, and Kenting National Park. Due to the island isolation, the proportions of endemic species are great in Taiwan, which also presents a high biodiversity. There are 4255 species of vascular plants including 1133 endemic. 5936 species in 1276 genera of fungi are hitherto reported in Taiwan. Among them, 233 Corticiaceae species were recorded, over one third (79 species) of them are known only from Taiwan. The first fungal report in Taiwan is about Phytophthora cyperi, published by the Japanese researcher T. Kawakami in 1904. Therefore, the history of research about fungi in Taiwan is more than one hundred years old. An eminent Japanese mycologist K. Sawada made an intensive survey from 1919 to 1959, and reported 2464 fungi species in his eleven volumes of “Descriptive Catalogue of Formosan Fungi”. However, only a few species (21 species in 9 genera) of Corticiaceae were recorded. From 1973, Chen and Lin resumed the study on Corticiaceae, and also some other foreign mycologists contributed for this field after 1980. The German research group lead by Franz Oberwinkler from Tübingen University collected in Taiwan several times. They published a number of new species and new records. Since 1989, S. H. Wu, a Taiwanese mycologist, has published a great amount of reports on corticioid fungi from Taiwan. Corticioid fungi were made up by the large and heterogeneous unnatural family Corticiaceae and other resupinate fungi belonging to other natural families in the Agaricomycetes. Molecular studies have shown that corticioid genera are distributed across all major clades of Agaricomycetes indicating that the corticioid fungi represent a polyphyletic group. They have resupinate fruitbodies and similar habitats. Species are characterized by simple fruitbody, more or less effused, and present smooth, porioid, grandinioid to odontioid hymenial surface. The fruitbodies are differently colored and usually soft to tough. Most of the Corticiaceae species are wood-saprobic organisms and gain the energy from the decomposing of wood-substrate such as cellulose or lignin. Materials for this study were collected by the author and other mycologists in Taiwan during surveys in April and May 1996, and March 2007, using the spring season with its high humidity and warm climate which are optimal conditions for the development of fungi. For assembling, the convenience sampling method was used in this study. This approach was chosen because it enables to detect a high biodiversity in a short time, and also to find species with rare or patchy distribution. The collecting sites from the North to the South include four National Parks and some preserved forests. They cover many different habitats such as low lands and high mountains. Fresh specimens were dried and analysed with a light microscope. 265 specimens belonging to Corticiaceae were studied in this research. Among them, 50 species in 21 genera including 11 new records and 10 new species were described with text and drawing. Four new species are belonging to Hyphodontia (H. sp. nov. 1, H. sp. nov. 2, H. sp. nov. 3, and H. sp. nov. 4), four to Schizopora (Sch. sp. nov. 1, Sch. sp. nov. 2, Sch. sp. nov. 3, and Sch. sp. nov. 4), one in Trechispora (T. sp. nov. 1), and one in Tubulicrinis (T. sp. nov. 1). Species recorded as new are Aleurodiscus amorphus, Botryohypochnus isabellinus, Hyphodontia cineracea, Hyphodontia palmae, Hypochnicium vellereum, Merulius tremellosus, Metulodontia nivea, Paullicorticium ansatum, Phlebia radiata, Phlebiella ardosiaca, and Xylobolus frustulatus. Besides, Botryohypochnus, Merulius, Metulodontia, Paullicorticium, and Xylobolus are also newly recorded genera in Taiwan. The genus Hyphodontia presents the highest diversity with 20 out of 50 species recorded. The second important genus is Hyphoderma, however with only 5 species. This indicates that Hyphodontia and Hyphoderma have a higher ability to develop in variable environments and approximately shows the predominance of these two genera in Taiwanese Corticiaceae. There are 11 new records out of the 50 species recorded, representing 22%. Some species, e.g. Hypochnicium vellereum and Paullicorticium ansatum were in the past recorded only in Europe and North America with cold and temperate climate. The samples of them are for the first time found in the subtropical belt, and display some difference from those of temperate regions. These collections should be molecularly investigated to clarify if they represent the same species of temperate areas. Patchily distributed species, for example Phlebiella ardosiaca, previously known only in Europe, and Hyphodontia palmae collected only in Brazil, were first recorded in different continents. Two possibilities are indicated by these new records: they are worldwide species but very rare to be found, or the Taiwanese specimens are taxonomically different. More survey from other continents and molecular study for these collections should be done in the future to solve this question. The distribution of Corticiaceae in Taiwan presents the variations in the north, central, and south areas and shows the diversity in lowlands and high mountains. The results of this study provide the evidence that the temperate Corticiaceae species displays a wider distribution. Subtropical and tropical taxa probably have also high dispersal capacities, and could possibly be found in the future in neighboring areas such as China, Japan, Korea or South Asia, but this needs further researches. In the total of 50 species, 10 new taxa were described in this study, giving about 20%. Some new species (e.g. Hyphodontia sp. 1, Hyphodontia sp. 2, and Hyphodontia sp. 3) are very similar to known species (Hyphodontia sambuci and Hyphodontia formosana), and the distinctive characters of Schizopora sp. nov. 1 are intermediate between those of Schizopora paradoxa and Hyphodontia flavipora. Thus, these small differences between the new and known species, suggest that the speciation occurred when the fungi migrated into Taiwan, due to the high diversity of environment, and amounts of the endemic plants. Taiwan is an intermediate place for the south (tropical) fungal species to migrate and adapt to north (temperate) regions. The middle and high altitude environments in Taiwan offer good conditions for the fungal speciation and possibly the occurrence of physiological changes to adapt to the temperate climate. Thus Taiwan has an important position for the biogeography of Asia mycobiota. 5936 known species in Taiwan represent about only 20% of the estimated number (24000) of Taiwanese fungal taxa. In this study, the findings (22% new records and 20% new species) indicate that amounts of unknown fungi species are expected in Taiwan. The lack of knowledge indicates that many new species are awaiting description, and fungal survey in Taiwan remains in a Pioneer phase. The last three wide surveys of Corticiaceae researches took place 20 years before this study (Chen & Lin 1977, Lin & Chen 1989, Wu 1990). After previous important contributions, the present taxonomic study comprising 21 genera is the most extensive on Corticiaceae of Taiwan.