Monoid generalizations of the Richard Thompson groups

The groups G_k,1 of Richard Thompson and Graham Higman can be generalized in a natural way to monoids, that we call M_k,1, and to inverse monoids, called ; this is done by simply generalizing bijections to partial functions or partial injective functions. The monoids M_k,1 have connections with circuit complexity (studied in other papers). Here we prove that M_k,1 and are congruence-simple for all k. Their Green relations J and D are characterized: M_k,1 and are J-0-simple, and they have k−1 non-zero D-classes. They are submonoids of the multiplicative part of the Cuntz algebra O_k. They are finitely generated, and their word problem over any finite generating set is in P. Their word problem is coNP-complete over certain infinite generating sets.     

Arbitrary vs. regular semigroups

The notion of regularity for semigroups is studied, and it is shown that an unambiguous semigroup (i.e., whose $\text{L}$ and $\text{R}$ orders are respectively unions of disjoint trees) can be embedded in a regular semigroup with the same subgroups and the same ideal structure (except that a zero is added to the regular semigroup).In a previous paper [1] it was shown that any semigroup is the homomorphic image of an unambiguous semigroup with the same groups and a similar ideal structure.Together these two papers thus prove that an arbitrary semigroup divides a regular semigroup with a similar structure.The resulting regular semigroup is finite (resp. torsion, or bounded torsion) if the given semigroup has that property.     

A cell-microelectronic sensing technique for profiling cytotoxicity of chemicals

A cell-microelectronic sensing technique is developed for profiling chemical cytotoxicity and is used to study different cytotoxic effects of the same class chemicals using nitrosamines as examples. This technique uses three human cell lines (T24 bladder, HepG2 liver, and A549 lung carcinoma cells) and Chinese hamster ovary (CHO-K1) cells in parallel as the living components of the sensors of a real-time cell electronic sensing (RT-CES) method for dynamic monitoring of chemical toxicity. The RT-CES technique measures changes in the impedance of individual microelectronic wells that is correlated linearly with changes in cell numbers during t log phase of cell growth, thus allowing determination of cytotoxicity. Four nitrosamines, N-nitrosodimethylamine (NDMA), N-nitrosodiphenylamine (NDPhA), N-nitrosopiperidine (NPip), and N-nitrosopyrrolidine (NPyr), were examined and unique cytotoxicity profiles were detected for each nitrosamine. In vitro cytotoxicity values (IC₅₀) for NDPhA (ranging from 0.6 to 1.9 mM) were significantly lower than the IC₅₀ values for the well-known carcinogen NDMA (15-95 mM) in all four cell lines. T24 cells were the most sensitive to nitrosamine exposure among the four cell lines tested (T24 > CHO > A549 > HepG2), suggesting that T24 may serve as a new sensitive model for cytotoxicity screening. Cell staining results confirmed that administration of the IC₅₀ concentration from the RT-CES experiments inhibited cell growth by 50% compared to the controls, indicating that the RT-CES method provides reliable measures of IC₅₀. Staining and cell-cycle analysis confirmed that NDPhA caused cell-cycle arrest at the G0/G1 phase, whereas NDMA did not disrupt the cell cycle but induced cell death, thus explaining the different cytotoxicity profiles detected by the RT-CES method. The parallel cytotoxicity profiling of nitrosamines on the four cell lines by the RT-CES method led to the discovery of the unique cytotoxicity of NDPhA causing cell-cycle arrest. This study demonstrates a new approach to comprehensive testing of chemical toxicity.     

A Complete Rewrite System and Normal Forms for (S) reg

The ( . ) _reg construction was introduced in order to make an arbitrary semigroup S divide a regular semigroup (S) _reg which shares some important properties with S (e.g., finiteness, subgroups, torsion bounds, J -order structure). We show that (S) _reg can be described by a rather simple complete string rewrite system , as a consequence of which we obtain a new proof of the normal form theorem for (S) _reg . The new proof of the normal form theorem is conceptually simpler than the previous proofs.     

Real-time cell-microelectronic sensing of nanoparticle-induced cytotoxic effects

We report a real-time cell analysis (RTCA) sensing method of 96 electronic microwells for profiling the cytotoxicity of nanoparticles on different cell lines. The method consists of 96 microwells embedded with microelectrodes (96x E-plate) to measure impedance changes of adherent cell lines. When the testing cells change in population, adhesion, and/or morphology, the impedance at the cell–electrode interface changes to provide real-time monitoring of overall cell status. To demonstrate this technique, we used three cell lines as sensing probes: two human lung carcinoma cell lines, A549 and SK-MES-1, and a normal mammalian cell line, CHO-K1. We tested two well-characterized nanoparticles: nano-titanium dioxide (nTiO₂) and nano-silver (nAg). The three cell lines were separately seeded into 96x E-plates and treated with varying concentrations of nanoparticles (0.078–160 μg mL⁻¹). This method provides dynamic cell response profiles and temporal IC₅₀ histograms, showing concentration-, time-, particle-, and cell-dependent cytotoxicity. The 24 h and 48 h IC₅₀ values of nAg obtained using both the RTCA and the neutral red uptake (NRU) assays were in good agreement, validating the RTCA technique. The RTCA assay does not suffer interference from nTiO₂, whereas the NRU assay cannot be used due to severe interference from nTiO₂. A cytostatic response was observed in CHO-K1 cells after 24 h exposure to 40 μg mL⁻¹ nTiO₂, which was correlated with S-phase cell cycle arrest based on cell cycle analysis using flow cytometry. This suggests that the shapes of the response curves provide indicative information, directing further studies into the mode of action of the toxicant. Advantages of the RTCA technique over traditional colorimetric assays for screening the cytotoxicity of nanoparticles include minimizing interference, qualitative and quantitative cytotoxicity data, and the capability of real-time and high-throughput measurements.     

Bernoulli measure on strings,and Thompson-Higman monoids

The Bernoulli measure on strings is used to define height functions for the dense R\mathcal{ R}- and L\mathcal{ L}-orders of the Thompson-Higman monoids M _k,1. The measure can also be used to characterize the D\mathcal{ D}-relation of certain submonoids of M _k,1. The computational complexity of computing the Bernoulli measure of certain sets, and in particular, of computing the R\mathcal{ R}- and L\mathcal{ L}-height of an element of M _k,1 is investigated.     

Monoids that map onto the Thompson-Higman groups

A slight modification of the definition of the Thompson-Higman groups G _k,1 and F _k,1 leads to inverse monoids that map onto G _k,1 (respectively F _k,1), and that have interesting properties: they are finitely generated, and residually finite. These inverse monoids are closely related to the suffix expansion of G _k,1 (respectively F _k,1).     

Two-letter group codes that preserve aperiodicity of inverse finite automata

We construct group codes over two letters (i.e., bases of subgroups of a two-generated free group) with special properties. Such group codes can be used for reducing algorithmic problems over large alphabets to algorithmic problems over a two-letter alphabet. Our group codes preserve aperiodicity of inverse finite automata. As an application we show that the following problems are PSpace-complete for two-letter alphabets (this was previously known for large enough finite alphabets): The intersection-emptiness problem for inverse finite automata, the aperiodicity problem for inverse finite automata, and the closure-under-radical problem for finitely generated subgroups of a free group. The membership problem for 3-generated inverse monoids is PSpace-complete. Both authors were supported in part by NSF grant DMS-9970471. The first author was also supported in part by NSF grant CCR-0310793. The second author acknowledges the support of the Excellency Center, “Group Theoretic Methods for the Study of Algebraic Varieties” of the Israeli Science Foundation.     

Almost finite expansions of arbitrary semigroups

We describe algebraic techniques that enable us to apply methods of finite semigroup theory to arbitrary infinite semigroups. This will be used in later papers to put global coordinates on semigroups and their morphisms, and to study languages and automata that are not finite-state.