Recognizable trace languages,distributed automata and the distribution problem

We introduce new finite state parallel machines, the (-)distributed automata, for trace languages. We prove that these machines give a new characterization of recognizable trace languages: a trace language is recognizable if and only if it is recognized by a (-)distributed automaton. At last, we show how the classical problem of distribution of uninterpreted tasks on several processors can be straightforward modelized by recognizable trace languages and solved using (-)distributed.This work has been partly supported by the ESPRIT Basic Research Actions N^o 3148 (DEMON) and by the PRC C³ and Math-Info     

Size-depth tradeoff in monotone Boolean formulae

Summary Formula size and depth are two important complexity measures of Boolean functions. We study the tradeoff between those two measures: We give an infinite set of Boolean functions and show for nearly each of them: There is no monotone formula computing it optimal with respect to both measures. We give a lower and upper bound on the product of size and depth of monotone formulae computing our functions. That implies, moreover, a logarithmic lower bound on circuit depth.Denotations the set of natural numbers {1,2,...} - for x>0, x =max{y{0}¦y¦<=x} - log logarithm to the base 2     

Sur les générateurs algébriques et linéaires

Résumé Nous étudions certaines propriétés des générateurs algébriques et linéaires. Nous montrons que le langage algébrique E engendré par la grammaire: S aSbSc + d domine tous les langages algébriques par applications séquentielles fidèles. Nous en déduisons que pour tout langage algébrique L et tout générateur algébrique L, il existe une transduction rationnelle fonctionnelle et fidèle telle que L=(L). Ce résultat, qui n'est pas vérifié pour la famille, Lin, des langages algébriques linéaires, nous permet de montrer qu'aucun générateur algébrique n'appartient à la famille EDTOL. Enfin, nous établissons que si L est un générateur linéaire, L # est un générateur séquentiel pour Lin.

---

Algebraic and linear generators

Summary We study some properties of algebraic and linear generators. We show that the algebraic language E generated by the grammar: S aSbSc + d dominates every algebraic language by faithful sequential mappings. We deduce that, for every algebraic language L and every algebraic generator L, there exists a faithful rational function such that L=(L). This result, which does not hold for the family of linear languages, permits us to show that no algebraic generator belongs to the family EDTOL. Also, we prove if L is a linear generator then L # is a sequential generator for Lin.

     

A useful lemma for context-free programmed grammars

We show that all quasi-realtime one-way multi-counter languages can be generated by a context-free -free programmed grammar (even under the free interpretation). The result can be used to obtain a new and almost trivial proof of the fundamental theorem that arbitrary context-free programmed grammars can generate all recursively enumerable languages. The proof of our result also yields the following, interesting characterization: the quasi-realtime one-way multi-counter languages are precisely the -limited homomorphic images of (free) context-free programmed production languages. It follows that the (free) derivation languages of context-free or even context-free programmed grammars, which were known to be context-sensitive, are in fact contained in the family of context-free -free programmed languages.     

On generators and generative capacity of EOL forms

Summary In this paper we study the generative capacity of EOL forms from two different points of view. On the one hand, we consider the generative capacity of special EOL forms which one could call linear like and context free like, establishing the existence of a rich variety of non-regular sub-EOL language families. On the other hand, we propose the notion of a generator L of a language family We mean by this that any synchronized EOL system generating L generates — if understood as an EOL form — all languages of . We characterize the generators of the family of regular languages, and prove that other well known language families do not have generators.Partially supported under NSE Research Council of Canada, grant No. A-7700     

On the usefulness of bifaithful rational cones

Roughly, a faithful (resp. bifaithful) rational transduction is a non deterministic finite state mapping that does not decrease (resp. alter) the length of words by very much. We introduce the notion of stronglyf-saturated language:L is stronglyf-saturated if and only if for any languageL, from which we can obtainL by faithful rational transduction, for any languageL, image ofL by a faithful rational transduction, there exists a bifaithful rational transduction such thatL is the image ofL . We prove that no quasirational language and no language in the substitution closed rational cone generated by bounded languages is stronglyf-saturated. Conversely, we establish that a language such as , very low in the hierarchy of algebraic languages, is stronglyf-saturated thus is not a quasirational language. We also establish that any commutative quasi rational language over two letters is rational.     

Bicentres de langages algébriques

Resume Les notions de bicentre et bicentre strict d'un langage, définies par A. De Luca, A. Restivo et S. Salemi généralisent la notion de centre d'un langage définie par M. Nivat. L'objet du présent papier est de répondre á la question suivante lorsque désigne la famille des langages algébriques ou l'une de ses sous-familles classiques:Si L appartient à , le bicentre de L (respectivement le bicentre strict de L) appartient-il à ?Le principal résultat est une réponse positive à cette question lorsqu'il s'agit de la notion de bicentre et que est un full-AFL uniforme de langages algébriques.

---

Bicenters of context-free languages

Summary The notions of bicenter and strict bicenter of a language have been defined by A. De Luca, A. Restivo and S. Salemi and are a generalisation of the notion of center of a language, defined by M, Nivat. This paper deals with the following question, when is the family of context-free languages or one of its classical subfamilies:when L is in , is the bicenter (resp. the strict bicenter) of L also in ?Concerning the notion of bicenter, the main result of the paper is a positive answer when is a uniform full-AFL of context-free languages.

     

A Hyperbase for Binary Lattice Hyperidentities

We define an identity to be hypersatisfied by a variety V if, whenever the operation symbols of V, are replaced by arbitrary terms (of appropriate arity) in the operations of V, the resulting identity is satisfied by V in the usual sense. Whenever the identity is hypersatisfied by a variety V, we shall say that is a V hyperidentity. For example, the identity x + x y = x (x + y) is hypersatisfied by the variety L of all lattices. A proof of this consists of a case-by-case examination of { + , } {x, y, x y, x y}, the set of all binary lattice terms. In an earlier work, we exhibited a hyperbase ^L for the set of all binary lattice (or, equivalently, quasilattice) hyperidentities of type 2, 2. In this paper we provide a greatly refined hyperbase _L . The proof that _L is a hyperbase was obtained by using the automated reasoning program Otter 3.0.4.     

Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.     

An extension of the theory of learning systems

Summary The author's inquiry [1] on learning systems is generalized in the following respects: The process of learning, instead of coming to an end when the learning goal has been reached, is supposed to last for ever, so that the above definitive learning as well as phenomena such as forgetting, re-learning, changing the goal etc. become describable.We take over the notion of semi-uniform solvability of a set of learning problems (2.2), but now (trivial cases excluded) the whole capacity of a learning system is never s. u. solvable. Finite such sets are. The notion of a solving-basis of some is introduced and we can state necessary conditions that possess such a basis (2.14), so that examples of sets without a basis can be provided. On the other hand, any s. u. solvable has as basis. The notion of uniform solvability (3.1) reinforces that of s. u. solvability, and there are given sufficient conditions for to be uniformly solvable (3.6). In some finite cases, s. u. solvability, existence of a basis and uniform solvability coincide (3.7–3.9). At last we give the construction for the weakest learning system solving a uniformly solvable problem set (3.12–3.19).Eine deutsche Fassung wurde am 30. Mai 1972 eingereicht.     

Relationships between pushdown automata with counters and complexity classes

In this paper a machine model is defined whose access to the storage cells is controlled by means of address registers. It is shown that every set acceptable by such a machine within time boundcn ^p,p , is accepted by a deterministic 2p-head two-way pushdown automaton which has additional counters of length log₂ n. On the other hand every set acceptable by a deterministicp-head two-way pushdown automaton can be accepted by this machine model within time boundcn ^plog₂ n. A result similar to one of the main theorems (theorem 4) of this paper has been proved also by S. A. Cook. Both proofs are based on the same idea but have been found independently.     

Well quasi-orders and regular languages

An extension of Myhill's theorem of automata theory, due to Ehrenfeucht et al. [4] shows that a subsetX of a semigroupsS is recognizable if and only ifX is closed with respect to a monotone well quasi-order onS. In this paper we prove that a similar extension of Nerode's theorem is not possible by showing that there exist non-regular languages on a binary alphabet which are closed with respect to a right-monotone well quasi-order. We give then some additional conditions under which a setX S closed with respect to a right-monotone well quasi-order becomes recognizable. We prove the following main proposition: A subsetX ofS is recognizable if and only ifX is closed with respect to two well quasi-orders<=₁ and<=₂ which are right-monotone and left-monotone, respectively. Some corollaries and applications are given. Moreover, we consider the family of all languages which are closed with respect to a right-monotone well quasi-order on a finitely generated free monoid. We prove that is closed under rational operations, intersection, inverse morphisms and direct non-erasing morphisms. This implies that is closed under faithful rational transductions. Finally we prove that the languages in satisfy a suitable pumping lemma and that contains languages which are not recursively enumerable.     

Searching minimax game trees under memory space constraint

Games such as CHESS, GO and OTHELLO can be represented by minimax game trees. Among various search procedures to solve such game trees,- and SSS^* are perhaps most well known. Although it is proved that SSS^* explores only a subset of the nodes explored by-, - is commonly believed to be faster in real applications, since it requires very little memory space and hence its storage management cost is low. Contrary to this folklore, however, this paper reports, using the OTHELLO game as an example, that SSS^* is much faster than-. It is also demonstrated that SSS^* can be modified to make the required memory space controllable to some extent, while retaining the high efficiency of the original SSS^*.This research was partially supported by the Ministry of Education, Science and Culture of Japan, under a Scientific Grant-in-Aid.     

The Objective Conception of Context and Its Logic

In this paper, an objective conception of contexts based loosely upon situation theory is developed and formalized. Unlike subjective conceptions, which take contexts to be something like sets of beliefs, contexts on the objective conception are taken to be complex, structured pieces of the world that (in general) contain individuals, other contexts, and propositions about them. An extended first-order language for this account is developed. The language contains complex terms for propositions, and the standard predicate ist that expresses the relation that holds between a context and a proposition just in case the latter is true in the former. The logic for the objective conception features a global classical predicate calculus, a local logic for reasoning within contexts, and axioms for propositions. The specter of paradox is banished from the logic by allowing ist to be nonbivalent in problematic cases: it is not in general the case, for any context c and proposition p, that either ist(c,p) or ist(c, ¬ p). An important representational capability of the logic is illustrated by proving an appropriately modified version of an illustrative theorem from McCarthy's classic Blocks World example.     

Efficient Solution of Multi-Term Fractional Differential Equations Using P(EC)<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>E Methods

We investigate strategies for the numerical solution of the initial value problem with initial conditions where 0<₁<₂<<. Here y ⁽ _j ) denotes the derivative of order _j >0 (not necessarily _j ) in the sense of Caputo. The methods are based on numerical integration techniques applied to an equivalent nonlinear and weakly singular Volterra integral equation. The classical approach leads to an algorithm with very high arithmetic complexity. Therefore we derive an alternative that leads to lower complexity without sacrificing too much precision. Mathematics Subject Classification: Primary 65L05; Secondary 65L06, 65L20     

Information Gaps as Communication Needs: A New Semantic Foundation for Some Non-Classical Logics

Semantics connected to some information based metaphor are well-known in logic literature: a paradigmatic example is Kripke semantic for Intuitionistic Logic. In this paper we start from the concrete problem of providing suitable logic-algebraic models for the calculus of attribute dependencies in Formal Contexts with information gaps and we obtain an intuitive model based on the notion of passage of information showing that Kleene algebras, semi-simple Nelson algebras, three-valued ukasiewicz algebras and Post algebras of order three are, in a sense, naturally and directly connected to partially defined information systems. In this way wecan provide for these logic-algebraic structures a raison dêetre different from the original motivations concerning, for instance, computability theory.     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.     

On computing Boolean connectives of characteristic functions

This paper is a study of the existence of polynomial time Boolean connective functions for languages. A languageL has an AND function if there is a polynomial timef such thatf(x,y) L x L andy L. L has an OR function if there is a polynomial timeg such thatg(x,y) xL oryL. While all NP complete sets have these functions, Graph Isomorphism, which is probably not complete, is also shown to have both AND and OR functions. The results in this paper characterize the complete sets for the classes D^p and p^SAT[O(logn)] in terms of AND and OR and relate these functions to the structure of the Boolean hierarchy and the query hierarchies. Also, this paper shows that the complete sets for the levels of the Boolean hierarchy above the second level cannot have AND or OR unless the polynomial hierarchy collapses. Finally, most of the structural properties of the Boolean hierarchy and query hierarchies are shown to depend only on the existence of AND and OR functions for the NP complete sets.The first author was supported in part by NSF Research Grants DCR-8520597 and CCR-88-23053, and by an IBM Graduate Fellowship.     

On parsing two-level grammars

Summary Making use of the fact that two-level grammars (TLGs) may be thought of as finite specification of context-free grammars (CFGs) with infinite sets of productions, known techniques for parsing CFGs are applied to TLGs by first specifying a canonical CFG G — called skeleton grammar — obtained from the cross-reference of the TLG G. Under very natural restrictions it can be shown that for these grammar pairs (G, G) there exists a 1 — 1 correspondence between leftmost derivations in G and leftmost derivations in G. With these results a straightforward parsing algorithm for restricted TLGs is given.     

Commutation with Ternary Sets of Words

We prove that for any nonperiodic set of words F \subseteq ⁺ with at most three elements, the centralizer of F, i.e., the largest set commuting with F, is F^*. Moreover, any set X commuting with F is of the form X = F^I, for some I \subseteq . A boundary point is thus established, as these results do not hold for all languages with at least four words. This solves a conjecture of Karhumäki and Petre, and provides positive answers to special cases of some intriguing questions on commutation of languages, raised by Ratoandromanana and Conway.