Search results for "Monad"
showing 10 items of 81 documents
Nondeterministic operations on finite relational structures
1998
Abstract This article builds on a tutorial introduction to universal algebra for language theory (Courcelle, Theoret. Comput. Sci. 163 (1996) 1–54) and extends it in two directions. First, nondeterministic operations are considered, i.e., operations which give a set of results instead of a single one. Most of their properties concerning recognizability and equational definability carry over from the ordinary case with minor modifications. Second, inductive sets of evaluations are studied in greater detail. It seems that they are handled most naturally in the framework presented here. We consider the analogues of top-down and bottom-up tree transducers. Again, most of their closure propertie…
The Monadic Quantifier Alternation Hierarchy over Grids and Graphs
2002
AbstractThe monadic second-order quantifier alternation hierarchy over the class of finite graphs is shown to be strict. The proof is based on automata theoretic ideas and starts from a restricted class of graph-like structures, namely finite two-dimensional grids. Considering grids where the width is a function of the height, we prove that the difference between the levels k+1 and k of the monadic hierarchy is witnessed by a set of grids where this function is (k+1)-fold exponential. We then transfer the hierarchy result to the class of directed (or undirected) graphs, using an encoding technique called strong reduction. It is notable that one can obtain sets of graphs which occur arbitrar…
The monadic quantifier alternation hierarchy over grids and pictures
1998
The subject of this paper is the expressive power of monadic second-order logic over two-dimensional grids. We give a new, self-contained game-theoretical proof of the nonexpressibility results of Matz and Thomas. As we show, this implies the strictness of the monadic second-order quantifier alternation hierarchy over grids.
Double adjunctions and free monads
2011
We characterize double adjunctions in terms of presheaves and universal squares, and then apply these characterizations to free monads and Eilenberg--Moore objects in double categories. We improve upon our earlier result in "Monads in Double Categories", JPAA 215:6, pages 1174-1197, 2011, to conclude: if a double category with cofolding admits the construction of free monads in its horizontal 2-category, then it also admits the construction of free monads as a double category. We also prove that a double category admits Eilenberg--Moore objects if and only if a certain parameterized presheaf is representable. Along the way, we develop parameterized presheaves on double categories and prove …
Local Normal Forms for First-Order Logic with Applications to Games and Automata
1999
Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x_1,...,x_l, \forall y, φ where φ is r-local around y, i.e. quantification in φ is restricted to elements of the universe of distance at most r from y. \par From this and related normal forms, variants of the Ehrenfeucht game for first-order and existential monadic second-order logic are developed that restrict the possible strategies for the spoiler, one of the two players. This makes proofs of the existence of a winning strategy for the duplicator, the other player, easier and can thus simplify inexpressibility proofs. \par As another application, automata mode…
Molecular phylogeny of parabasalids with emphasis on the order Cristamonadida and its complex morphological evolution
2009
1055-7903 doi: DOI: 10.1016/j.ympev.2009.03.011; Parabasalia represents a complex assemblage of species, which recently received extensive reorganization. The newly created order Cristamonadida unites complex hypermastigids belonging to the Lophomonadida like the joeniids, the multinucleate polymonad Calonymphidae, and well-developed trichomonads in the Devescovinidae. All these protists exclusively occur in the guts of termites and related insects. In this study, small subunit rRNA and glyceraldehyde-3-phosphate dehydrogenase genes were identified without cultivation from 14 species in Cristamonadida including previously unstudied genera such as Joenina, Joenia, Joenoides, Macrotrichomonas…
Real-time PCR detection of Pseudomonas aeruginosa in clinical and municipal wastewater and genotyping of the ciprofloxacin-resistant isolates
2006
Real-time quantification of Pseudomonas aeruginosa was performed in various wastewater systems including clinical, municipal wastewaters and inflow from a wastewater treatment plant. The highest concentrations of P. aeruginosa-specific targets were detected in clinical wastewaters. Limitations of the detection system resulting from inhibition or cross-reaction were identified. Ciprofloxacin-resistant P. aeruginosa strains were isolated after specific enrichment from clinical and municipal wastewaters. In some cases they were also cultivated from effluent of a wastewater treatment plant, and from its downstream river water. A total of 119 isolates were phenotypically characterized as ciprofl…
Phylogenetic relationships within the family Halomonadaceae based on comparative 23S and 16S rRNA gene sequence analysis.
2010
A phylogenetic study of the family Halomonadaceae was carried out based on complete 16S rRNA and 23S rRNA gene sequences. Several 16S rRNA genes of type strains were resequenced, and 28 new sequences of the 23S rRNA gene were obtained. Currently, the family includes nine genera (Carnimonas, Chromohalobacter, Cobetia, Halomonas, Halotalea, Kushneria, Modicisalibacter, Salinicola and Zymobacter). These genera are phylogenetically coherent except Halomonas, which is polyphyletic. This genus comprises two clearly distinguished clusters: group 1 includes Halomonas elongata (the type species) and the species Halomonas eurihalina, H. caseinilytica, H. halmophila, H. sabkhae, H. almeriensis, H. hal…
The evolutionary origin of Xanthomonadales genomes and the nature of the horizontal gene transfer process.
2006
Determining the influence of horizontal gene transfer (HGT) on phylogenomic analyses and the retrieval of a tree of life is relevant for our understanding of microbial genome evolution. It is particularly difficult to differentiate between phylogenetic incongruence due to noise and that resulting from HGT. We have performed a large-scale, detailed evolutionary analysis of the different phylogenetic signals present in the genomes of Xanthomonadales, a group of Proteobacteria. We show that the presence of phylogenetic noise is not an obstacle to infer past and present HGTs during their evolution. The scenario derived from this analysis and other recently published reports reflect the confound…
Effect of Pseudomonas sp. MT5 baths on Flavobacterium columnare infection of rainbow trout and on microbial diversity on fish skin and gills
2005
Use of Pseudomonas sp. strain MT5 to prevent and treat Flavobacterium columnare infection was studied in 2 experiments with fingerling rainbow trout Oncorhynchus mykiss. In the first experiment, length heterogeneity analysis of PCR-amplified DNA fragments (LH-PCR) was used to assess the effect of antagonistic baths on the microbial diversity of healthy and experimentally infected fish. In the 148 samples studied, no difference was found between bathed and unbathed fish, and 3 fragment lengths were detected most frequently: 500 (in 75.7% of the samples), 523 (62.2%) and 517 bp (40.5%). The species contributing to these fragment sizes were Pseudomonas sp., Rhodococcus sp. and F. columnare, re…