Disjunctive splittability of languages

Decompositions of languages over a finite alphabetX are investigated. Let T be a class of languages overX satisfying the following condition: (#) T contains at least one dense language, and every dense subset of an element in T is again in T. A language is said to be DT-splittable if it is a disjoint union of infinitely many discrete disjunctive languages in T which are locally finite of rank 1. It is shown that a language is DT-splittable if and only if it is a union of dense languages in T. The class P of all prefix codes satisfies the condition (#). DP-splittability of languages is investigated in detail. A language A is said to besemi-DT-splittable if A\F is DT-splittable for some finite languageF. Semi-DP-splittability is investigated. Semi-DP-splittability of catenations of languages is also studied.     

相对不可约合作系统解的单调性

合作系统是一类重要的动力系统,本世纪八十年代Hirsch曾就不可约合作系统给出了一系列重要结论,但在实际问题中有许多合作系统不是不可约的却具有不可约合作系统的性质,本文提出了比不可约性更广的相对不可约概念,指出这类系统的解与严格不可约系统的解同样具有强单调性,并给出严格的证明,从而将Hirsch的结果做了进一步推广,最后介绍凝血系统中相对不可约合作系统的应用实例。     

HARVESTING A TWO-PATCH PREDATOR-PREY METAPOPULATION

ABSTRACT. A mathematical model for a two-patch predator-prey metapoplation is developed as a generalization of single-species metapopulation harvesting theory. We find optimal harvesting strategies using dynamic programming and La-grange multipliers. If predator economic efficiency is relatively high, then we should protect a relative source prey subpopulation in two different ways: directly, with a higher escapement of the relative source prey subpopulation, and indirectly, with a lower escapement of the predator living in the same patch as the relative source prey subpopulation. Numerical examples show that if the growth of the predator is relatively low and there is no difference between prey and predator prices, then it may be optimal to harvest the predator to extinction. While, if the predator is more valuable compared to the prey, then it may be optimal to leave the relative exporter prey subpopulation unharvested. We also discuss how a ‘negative’ harvest might be optimal. A negative harvest might be considered a seeding strategy.     

On the Knowledge Complexity of

We show that if a language has an interactive proof of logarithmic statistical knowledge-complexity, then it belongs to the class . Thus, if the polynomial time hierarchy does not collapse, then -complete languages do not have logarithmic knowledge complexity. Prior to this work, there was no indication that would contradict languages being proven with even one bit of knowledge. Our result is a common generalization of two previous results: The first asserts that statistical zero knowledge is contained in [11, 2], while the second asserts that the languages recognizable in logarithmic statistical knowledge complexity are in [19]. Next, we consider the relation between the error probability and the knowledge complexity of an interactive proof. Note that reducing the error probability via repetition is not free: it may increase the knowledge complexity. We show that if the negligible error probability is less than (where k(n) is the knowledge complexity) then the language proven is in the third level of the polynomial time hierarchy (specifically, it is in ). In the standard setting of negligible error probability, there exist PSPACE-complete languages which have sub-linear knowledge complexity. However, if we insist, for example, that the error probability is less than , then PSPACE-complete languages do not have sub-quadratic knowledge complexity, unless . In order to prove our main result, we develop an AM protocol for checking that a samplable distribution D has a given entropy h. For any fractions , the verifier runs in time polynomial in and and fails with probability at most to detect an additive error in the entropy. We believe that this protocol is of independent interest. Subsequent to our work Goldreich and Vadhan [16] established that the problem of comparing the entropies of two samplable distributions if they are noticeably different is a natural complete promise problem for the class of statistical zero knowledge (). Received January 6, 2000 RID=" " ID=" " This research was performed while the authors were visiting the Computer Science Department at the University of Toronto, preliminary version of this paper appeared in [27] RID="*" ID="*" Partially supported by Technion V. P. R. Found––N. Haar and R. Zinn Research Fund. RID="†" ID="†" Partially supported by the grants OTKA T-029255, T-030059, FKFP 0607/1999, and AKP 2000-78 2.1.     

Restorations of punctured languages and similarity of languages

Punctured languages are languages whose words are partial words in the sense that the letters at some positions are unknown. We investigate to which extent restoration of punctured languages is possible if the number of unknown positions or the proportion of unknown positions per word, respectively, is bounded, and we study their relationships for different boundings. The considered restoration classes coincide with similarity classes according to some kind of similarity for languages. Thus all results we can also formulate in the language of similarity. We show some hierarchies of similarity classes for each class from the Chomsky hierarchy and prove the existence of linear languages which are not δ ‐similar to any regular language for any δ < ½. For δ ≥ ½ this is unknown but it could only be possible in the case of non‐slender linear languages. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Representing Utility Functions via Weighted Goals

We analyze the expressivity, succinctness, and complexity of a family of languages based on weighted propositional formulas for the representation of utility functions. The central idea underlying this form of preference modeling is to associate numerical weights with goals specified in terms of propositional formulas, and to compute the utility value of an alternative as the sum of the weights of the goals it satisfies. We define a large number of representation languages based on this idea, each characterized by a set of restrictions on the syntax of formulas and the range of weights. Our aims are threefold. First, for each language we try to identify the class of utility functions it can express. Second, when different languages can express the same class of utility functions, one may allow for a more succinct representation than another. Therefore, we analyze the relative succinctness of languages. Third, for each language we study the computational complexity of the problem of finding the most preferred alternative given a utility function expressed in that language (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Regular Component Splittable Languages

Every infinite regular language contains a regular subset of the formuv+w for some words u, v, w, where v is not the empty word. The regularsubsets of the above form are called regular components. Some well-knowncontext-free languages, such as the Dyck language and the balanced language(over an alphabet X with |X| = 2), are decomposed as disjointunions of disjunctive languages. In this paper, we investigate thedecompositions of some of the regular languages and the context-freelanguages as disjoint unions of regular components. An infinite language iscalled regular component splittable if it can be expressed as a disjointunion of regular components and a finite set. We show that the Dycklanguage, the balanced language and some disjunctive context-free splittablelanguages are regular component splittable. We also present an example toshow that there is a disjunctive context-free language which is not regularcomponent splittable.     

ECONOMIC MODELING OF THE PERSISTENCE OF ANTIMICROBIAL RESISTANCE

Abstract According to the dynamic relationship between antibiotic use and the incidence of multidrug‐resistant bacteria, the effectiveness of antibiotics is characterized as a natural resource exploited by antibiotic use. A major question is whether antibiotic effectiveness should be considered a renewable or an exhaustible resource. This paper presents a model combining epidemiological aspects of the decrease of resistance over time with an economic approach, modeling antimicrobial resistance as a negative externality of antibiotic use. The article concludes that the relative fitness of resistant bacteria is one driving factor for an estimation of the externality. If we, for instance, assume a low degree of relative fitness of resistant bacteria it is shown that resistance decreases fastest directly after antibiotic treatment. Accordingly, cycling of nonidentical drugs improves antibiotic effectiveness because cycling lowers the frequency of use of the individual antibiotic. In this case, antibiotic effectiveness must be characterized as a renewable resource in much the same way as a stock of fish in a lake. In contrast, if we assume a high degree of relative fitness of resistant bacteria, antibiotic effectiveness must be treated as an exhaustible resource because it is declined by every use of antibiotics.     

On permutative grammars generating context-free languages

A grammar is said to be permutative if it has permutation productions of the formAB BA in addition to context-free productions. Szilard languages and label languages are studied as examples of languages generable by permutative grammars. Particularly, sufficient conditions for a permutative grammar to generate a context-free language are studied.This work was supported by the Academy of Finland.     

INSTANCES AND RAMIFICATIONS OF THE SEMI-ADJOINT SITUATION I. PRESTABLE REFLECTION AND SYMMETRIC UNADS

Abstract

It is well known that there is a one to one correspondence between idempotent monads in a category and reflective subcategories. In this paper it is examined what replaces the reflective subcategory if the idempotent monad is replaced (a) by a monad and (b) by a symmetric unad. It is shown that in case (a) one obtains the weakly reflective subcategory of objects injective relative to the functor part of the monad. In case (b) one obtains a proto-reflection and it is shown that (for complete categories) the associated orthogonal subcategory is reflective if and only if there exists a free monad associated to the unad.     

A SIMPLE EXAMPLE OF A NON-FINITELY BASED SYSTEM OF POLYNOMIAL IDENTITIES

ABSTRACT

A system of polynomial identities is called finitely based if it is equivalent to some finite system of polynomial identities. Every system of polynomial identities in associative algebras over a field of characteristic 0 is finitely based: this is a celebrated result of Kemer. The first non-finitely based systems of polynomial identities in associative algebras over a field of a prime characteristic have been constructed recently by Belov, Grishin and Shchigolev. These systems of identities are relatively complicated. In the present paper we construct a simpler example of such a system and give a simple self-contained proof of the fact that the system is non-finitely based.     

Relative congruence formulas and decompositions in quasivarieties

Quasivarietal analogues of uniform congruence schemes are discussed, and their relationship with the equational definability of principal relative congruences (EDPRC) is established, along with their significance for relative congruences on subalgebras of products. Generalizing the situation in varieties, we prove that a quasivariety is relatively ideal iff it has EDPRC; it is relatively filtral iff it is relatively semisimple with EDPRC. As an application, it is shown that a finitary sentential logic, algebraized by a quasivariety K, has a classical inconsistency lemma if and only if K is relatively filtral and the subalgebras of its nontrivial members are nontrivial. A concrete instance of this result is exhibited, in which K is not a variety. Finally, for quasivarieties \({\sf{M} \subseteq \sf{K}}\), we supply some conditions under which M is the restriction to K of a variety, assuming that K has EDPRC.     

Combinatorial properties of boundary NLC graph languages

Node label controlled (NLC) grammars are graph grammars (operating on node labeled undirected graphs)which rewrite single nodes only and establish connections between the embedded graph and the neighbors of the rewritten node on the basis of the labels of the involved nodes only. They define (possibly infinite) languages of undirected node labeled graphs (or, if we just omit the labels, languages of unlabeled graphs). Boundary NLC (BNLC) grammars are NLC grammars with the property that whenever - in a graph already generated - two nodes may be rewritten, then these nodes are not adjacent. The graph languages generated by this type of grammars are called BNLC languages.In this paper we investigate the behaviour of graph invariants within BNLC languages. First we demonstrate that there is a dependency between the chromatic number and the clique number of graphs in BNLC languages (while this is wellknown not to be true for arbitrary graph languages). Secondly, we introduce a new graph invariant, the so-called index of a graph which seems to be very suitable for describing the adjacency structure of a graph. Then we prove that every BNLC language is of bounded index (which is shown not to be true for arbitrary graph languages). Thus we exhibit properties (concerning graph invariants) of BNLC languages which are intrinsic to this class. We use them to demonstrate that certain graph languages are not BNLC languages.     

相对半投射和直投射模

In this paper, the ＂relative＂ version of semi-projectivity is considered. Let M and N be modules. N is called M-semi-projective, if any homomorphism from N to an M-eyclie submodule f（M） of N can be factored through to a homomorphism from N to M and f, where f∈[M, N]. Some properties of relative semi-projectivity are obtained. Next, we consider a wider class of ＂elatively semi-projective＂ modules such as ＂elatively direct-projective＂ modules which were introduced by Nicholson and Zhou. Several properties of their homomorphisms are also obtained.     

The sequence of open and closed prefixes of a Sturmian word

A finite word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences, otherwise it is open. We are interested in the oc-sequence of a word, which is the binary sequence whose n-th element is 0 if the prefix of length n of the word is open, or 1 if it is closed. We exhibit results showing that this sequence is deeply related to the combinatorial and periodic structure of a word. In the case of Sturmian words, we show that these are uniquely determined (up to renaming letters) by their oc-sequence. Moreover, we prove that the class of finite Sturmian words is a maximal element with this property in the class of binary factorial languages. We then discuss several aspects of Sturmian words that can be expressed through this sequence. Finally, we provide a linear-time algorithm that computes the oc-sequence of a finite word, and a linear-time algorithm that reconstructs a finite Sturmian word from its oc-sequence.     

Baseline models are not “finishline” models: A sympathetic critique of Mayhew's strategy

A rationalist view of Relative Deprivation is possible if it is represented with extended preference. In the social movements studies, the concept of relative deprivation has been treated as an intervening variable, which is determined by the interpersonal comparisons and causes the social movements. The most important problem is whether a relatively deprived individual has an incentive for social movements or not. On the one hand he has different reference persons to whom he experiences relative deprivation and a sense of his subjective welfare, which make him behave in respective ways. But on the other hand he can behave in only one way at one time. We formalize the concept of the relative deprivation and construct the model that the relative deprivation and his preference in the ordinary sense are both the factors determining his behavior. Then it is deduced that there's no effect of the feeling relative deprivation for each individual to decide his way under some adequate conditions. So it should be concluded that the concept of the relative deprivation is not effective to explain social movements or social change in collectivities.     

A NOTE ON THE RELATIVE CANONICAL IMAGE OF A NON－HYPERELLIPTIC FIBRATION OF GENUS 4

ＡＮＯＴＥＯＮＴＨＥＲＥＬＡＴＩＶＥＣＡＮＯＮＩＣＡＬＩＭＡＧＥＯＦＡＮＯＮ－ＨＹＰＥＲＥＬＬＩＰＴＩＣＦＩＢＲＡＴＩＯＮＯＦＧＥＮＵＳ４￥ＣＨＥＮＺＨＩＪＩＥＡｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｉｎｖｅｓｔｉｇａｔｅｓｔｈｅｒｅｌａｔｉｖｅ１－ｃａ...     

On (ɛ,k)-normal words in connecting dynamical systems

The theorem of Copeland and Erdös on normal numbers relative to an integer base is generalised to infinite sequences composed of words from a certain class of languages. In particular, this proves the Copeland—Erdös result relative to a Pisot number as base.     

局部Noether模的相对连续性特征

设M是左R-模,本文证明了M是局部Noether的当且仅当σ[M]中的任意M-内射左R-模的直和是S∧2-连续的（S∧2-拟连续的）。     

Colored operads,series on colored operads,and combinatorial generating systems

We introduce bud generating systems, which are used for combinatorial generation. They specify sets of various kinds of combinatorial objects, called languages. They can emulate context-free grammars, regular tree grammars, and synchronous grammars, allowing us to work with all these generating systems in a unified way. The theory of bud generating systems uses colored operads. Indeed, an object is generated by a bud generating system if it satisfies a certain equation in a colored operad. To compute the generating series of the languages of bud generating systems, we introduce formal power series on colored operads and several operations on these. Series on colored operads are crucial to express the languages specified by bud generating systems and allow us to enumerate combinatorial objects with respect to some statistics. Some examples of bud generating systems are constructed; in particular to specify some sorts of balanced trees and to obtain recursive formulas enumerating these.