Search

We introduce and study the model of diving queue automata which are basically finite automata equipped with a storage medium that is organized as a queue. Additionally, two queue heads are provided at both ends of the queue that can move in a read-only mode inside the queue. In particular, we consider suitable time constraints and the case where only a finite number of turns on the queue is allowed. As one main result we obtain a proper queue head hierarchy, that is, two heads are better than one head, and one head is better than no head. Moreover, it is shown that the model with one queue head, finitely many turns, and no time constraints as well as the model with two queue heads, possibly infinitely many turns, and time constraints is captured by P and has a P-complete membership problem. We obtain also that a subclass of the model with two queue heads is already captured by logarithmic space. Finally, we consider decidability questions and it turns out that almost nothing is decidable for the model with two queue heads, whereas we obtain that at least emptiness and finiteness are decidable for subclasses of the model with one queue head.

We introduce a new variant of insertion systems, namely bonded insertion systems. In such systems, words are not only formed by usual letters but also by bonds between letters. Words which can be inserted, have “free” bonds at their ends which control at which positions in a word they can be inserted (namely only there, where the bonds “fit”). Two kinds of bonded insertion systems are defined in this paper: so-called bonded sequential insertion systems and bonded parallel insertion systems. In a sequential system, there is only one word inserted at a time. In a parallel system, there is a word inserted at every possible position in parallel in one time step. We investigate the generative capacity of those two kinds and relate the families of generated languages to some families of the Chomsky hierarchy and to families of languages generated by Lindenmayer systems. Additionally, we investigate some closure properties.

We investigate the open problem to characterize whether the infinite power of a given language is generated by an ω-code. In case the given language is a code (i.e. zero-relation language), the problem was solved. In this work, we solve the problem for the class of one-relation languages.

Pattern avoidance is an important research topic in combinatorics on words which dates back to Thue’s construction of an infinite word over three letters that avoids squares, i.e. , a sequence with no two adjacent identical factors. This result finds applications in various algebraic contexts where more general patterns than squares are considered. A more general form of pattern avoidance has recently emerged to allow for undefined positions in sequences. New concepts on patterns such as depth have been introduced and a number of questions have been raised, some of them we answer. In the process, we prove a strict bound on the number of square occurrences in an unavoidable pattern, and consequently, any pattern with more square occurrences than distinct variables is avoidable over three letters. We also provide an algorithm that determines whether a given pattern is of bounded depth, and if so, computes its depth.

Systems of equations of the form X i = ϕ i (X 1 , ... , X n ), for 1 ⩽ i ⩽ n , in which the unknowns X i are formal languages, and the right-hand sides ϕ i may contain concatenation and union, are known for representing context-free grammars. If, instead of union only, another set of Boolean operations is used, the expressive power of such equations may change: for example, using both union and intersection leads to conjunctive grammars [A. Okhotin, J. Automata, Languages and Combinatorics 6 (2001) 519–535], whereas using all Boolean operations allows all recursive sets to be expressed by unique solutions [A. Okhotin, Decision problems for language equations with Boolean operations, Automata, Languages and Programming, ICALP 2003, Eindhoven, The Netherlands, 239–251]. This paper investigates the expressive power of such equations with any possible set of Boolean operations. It is determined that different sets of Boolean operations give rise to exactly seven families of formal languages: the recursive languages, the conjunctive languages, the context-free languages, a certain family incomparable with the context-free languages, as well as three subregular families.

Several types of systems of parallel communicating restarting automata are introduced and studied. The main result shows that, for all types of restarting automata X, centralized systems of restarting automata of type X have the same computational power as non-centralized systems of restarting automata of the same type and the same number of components. This result is proved by a direct simulation. In addition, it is shown that for one-way restarting automata without auxiliary symbols, systems of degree at least two are more powerful than the component automata themselves. Finally, a lower and an upper bound are given for the expressive power of systems of parallel communicating restarting automata.

In this paper, we introduce generating networks of splicing processors (GNSP for short), a formal languages generating model related to networks of evolutionary processors and to accepting networks of splicing processors. We show that all recursively enumerable languages can be generated by GNSPs with only nine processors. We also show, by direct simulation, that two other variants of this computing model, where the communication between processors is conducted in different ways, have the same computational power.

We study hybrid systems with strong resets from the perspective of formal language theory. We define a notion of hybrid regular expression and prove a Kleene-like theorem for hybrid systems. We also prove the closure of these systems under determinisation and complementation. Finally, we prove that the reachability problem is undecidable for synchronized products of hybrid systems.

Mainstream object-oriented languages often fail to provide complete powerful features altogether, such as, multiple inheritance, dynamic overloading and copy semantics of inheritance. In this paper we present a core object-oriented imperative language that integrates all these features in a formal framework. We define a static type system and a translation of the language into the meta-language λ_object, , in order to account for semantic issues and prove type safety of our proposal.

This paper discusses context-free rewriting systems in which there exist two disjoint finite sets of rules, and a symbol, referred to as a condition of applicability, is attached to each rule in either of these two sets. In one set, a rule with a symbol attached to it is applicable if the attached symbol occurs in the current rewritten string while in the other set, such a rule is applicable if the attached symbol does not occur there. The present paper demonstrates that these rewriting systems are computationally complete. From this main result, the paper derives several consequences and solves several open problems.

We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.

We study the problem of learning regular tree languages from text. We show that the framework of function distinguishability, as introduced by the author in [ Theoret. Comput. Sci. 290 (2003) 1679–1711], can be generalized from the case of string languages towards tree languages. This provides a large source of identifiable classes of regular tree languages. Each of these classes can be characterized in various ways. Moreover, we present a generic inference algorithm with polynomial update time and prove its correctness. In this way, we generalize previous works of Angluin, Sakakibara and ourselves. Moreover, we show that this way all regular tree languages can be approximately identified.

We give necessary and sufficient conditions for a language to be the language of finite words that occur infinitely many times in an infinite word.

This paper proposes an operational semantics for value recursion in the context of monadic metalanguages. Our technique for combining value recursion with computational effects works uniformly for all monads. The operational nature of our approach is related to the implementation of recursion in Scheme and its monadic version proposed by Friedman and Sabry, but it defines a different semantics and does not rely on assignments. When contrasted to the axiomatic approach proposed by Erkok and Launchbury, our semantics for the continuation monad invalidates one of the axioms, adding to the evidence that this axiom is problematic in the presence of continuations.

The basic framework of domain μ-calculus was formulated in [39] more than ten years ago. This paper provides an improved formulation of a fragment of the μ-calculus without function space or powerdomain constructions, and studies some open problems related to this μ-calculus such as decidability and expressive power. A class of language equations is introduced for encoding μ-formulas in order to derive results related to decidability and expressive power of non-trivial fragments of the domain μ-calculus. The existence and uniqueness of solutions to this class of language equations constitute an important component of this approach. Our formulation is based on the recent work of Leiss [23], who established a sophisticated framework for solving language equations using Boolean automata (a.k.a. alternating automata [12, 35]) and a generalized notion of language derivatives. Additionally, the early notion of even-linear grammars is adopted here to treat another fragment of the domain μ-calculus.

Processes in Place/Transition (P/T) nets are defined inductively by a peculiar numbering of place occurrences. Along with an associative sequential composition called catenation and a neutral process, a monoid of processes is obtained. The power algebra of this monoid contains all process languages with appropriate operations on them. Hence the problems of analysis and synthesis, analogous to those in the formal languages and automata theory, arise. Here, the analysis problem is: for a given P/T net with an initial marking find the set of all processes the net may evoke. The synthesis problem is: given a process language L decide if there exists a marked net whose evolutions (represented by processes) are collected in L and, in the positive case, find such net and its initial marking. The problems are posed and given a general solution.

A shuffle ideal is a language which is a finite union of languages of the form A*a1 A*...A*ak where A is a finite alphabet and the a i 's are letters. We show how to represent shuffle ideals by special automata and how to compute these representations. We also give a temporal logic characterization of shuffle ideals and we study its expressive power over infinite words. We characterize the complexity of deciding whether a language is a shuffle ideal and we give a new quadratic algorithm for this problem. Finally we also present a characterization by subwords of the minimal automaton of a shuffle ideal and study the complexity of basic operations on shuffle ideals.

Advanced instrumentation, dealing with nanoscale technology at the current edge of human scientific enquiry, like X-Ray CT, generates an enormous quantity of data from single experiment. The very best modern lossless data compression algorithms use standard approaches and are unable to match high end requirements for mission critical application with full information conservation (a few pixels may vary by com/decom processing). In previous papers published elsewhere, we have already shown that traditional Q Arithmetic can be regarded as a highly sophisticated open logic, powerful and flexible bidirectional formal language of languages, according to “Computational Information Conservation Theory” ( CICT ). This new awareness can offer competitive approach to guide more convenient algorithm development and application for combinatorial lossless compression. To achieve true lossless com/decom and to overcome traditional constraints, the universal modular arithmetic approach, based on CICT Solid Number (SN) concept, is presented. To check practical implementation performance and effectiveness, an example on computational imaging is benchmarked by key performance index and compared to standard well-known lossless compression techniques. Results are critically discussed.

We prove that a word of length n from a finitely ambiguous context-free language can be generated at random under uniform distribution in O (n 2 log n ) time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time 1 -NAuxPDA with polynomially bounded ambiguity.

We prove that for each positive integer n, the finite commutative language En = c (a 1 a 2 ...an ) possesses a test set of size at most 5n. Moreover, it is shown that each test set for E n has at least n -1 elements. The result is then generalized to commutative languages L containing a word w such that (i) alph(w ) = alph}(L ); and (ii) each symbol a ∈ alph}(L ) occurs at least twice in w if it occurs at least twice in some word of L : each such L possesses a test set of size 11n , where n = Card(alph(L )). The considerations rest on the analysis of some basic types of word equations.

Natural algorithms to compute rational expressions for recognizable languages, even those which work well in practice, may produce very long expressions. So, aiming towards the computation of the commutative image of a recognizable language, one should avoid passing through an expression produced this way. We modify here one of those algorithms in order to compute directly a semilinear expression for the commutative image of a recognizable language. We also give a second modification of the algorithm which allows the direct computation of the closure in the profinite topology of the commutative image. As an application, we give a modification of an algorithm for computing the Abelian kernel of a finite monoid obtained by the author in 1998 which is much more efficient in practice.

Schoning [14] introduced a notion of helping and suggested the study of the class P help (C) of the languages that can be helped by oracles in a given class C. Later, Ko [12], in order to study the connections between helping and witness searching, introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call SH which contains all the self-helping classes. We introduce the Helping hierarchy whose levels are obtained applying a constant number of times the operator P help (.) to the set of all the languages. We show that the Helping hierarchy collapses to the k-th level if and only if SH is equal to the k-th level. We give characterizations of all the levels and use these to construct a relativized world in which the Helping hierarchy is infinite.

We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form $L\cap R$ , with a shuffle language L and a regular language R , contains non-semilinear languages and does not form a family of mildly context- sensitive languages.

We determine minimal elements, i.e. , atoms, in certain partial orders of factor closed languages under ⊆ . This is in analogy to structural Ramsey theory which determines minimal structures in partial orders under embedding.

International audience; The Rabin index of a rational language of infinite words given by a parity automaton with n states is computable in time O(n(2)c) where c is the cardinality of the alphabet. The number of values used by a parity acceptance condition is always greater than the Rabin index and conversely, the acceptance condition of a parity automaton can always be replaced by an equivalent acceptance condition whose number of used values is exactly the Rabin index. This new acceptance condition can also be computed in time O(n(2)C).

In [6] it was shown that shuffle languages are contained in one-way-NSPACE (log n ) and in P . In this paper we show that nondeterministic one-way logarithmic space is in some sense the lower bound for accepting shuffle languages. Namely, we show that there exists a shuffle language which is not accepted by any deterministic one-way Turing machine with space bounded by a sublinear function, and that there exists a shuffle language which is not accepted with less than logarithmic space even if we allow two-way nondeterministic Turing machines.

A simplified proof is given for the following result due to Lisovik: it is undecidable for two given e –free finite substitutions, whether they are equivalent on the regular language b {0,1}* c .

In this paper, the identification of stochastic regular languages is addressed. For this purpose, we propose a class of algorithms which allow for the identification of the structure of the minimal stochastic automaton generating the language. It is shown that the time needed grows only linearly with the size of the sample set and a measure of the complexity of the task is provided. Experimentally, our implementation proves very fast for application purposes.

International audience; If we consider words over the alphabet which is the set of all elements of a semigroup S, then such a word determines an element of S: the product of the letters of the word. S is strongly locally testable if whenever two words over the alphabet S have the same factors of a fixed length k, then the products of the letters of these words are equal. We had previously proved in [19] that the syntactic semigroup of a rational language L is strongly locally testable if and only if L is both locally and piecewise testable. We characterize in this paper the variety of strongly locally testable semigroups with commuting idempotents and, using the theory of implicit operations on a variety of semigroups, we derive an elementary combinatorial description of the related variety of languages.

On s'interesse ici aux langages que peuvent reconnaitre les groupoides dont le monoide multiplicatif appartient a la variete A 1 des monoides idempotents. On demontre que ceux ci reconnaissent un sous-ensemble strict de la classe des langages sans etoile. On etudie ensuite les groupoides contenant une identite (quasimonoides), on montre alors des relations d'inclusion stricte entre les classes de langages definies en specifiant que le monoide multiplicatif appartient aux varietes J 1 , R 1 et A 1 .

It is proved that any commutative language over an alphabet of n symbols possesses a test set of size O (n 2 ). If the Parikh-map of the language is a linear set, then the minimum size of the test set is O (n log n). A finite commutative language over an alphabet of n symbols such that the smallest test set for the language is of size Ω (n 2 ) is shown to exist.

In this paper a formalism is proposed, named fair expressions, partly introduced in [Bre94], that extends regular expressions to lists, having strings as components. This formalism uses classical regular operators, i.e. catenation and its closure, and novel ones, namely the operator of merge and its closure, which are natural for lists. Fair expressions allow to define languages of lists, named fair languages, which can be compared to word languages by flattening the lists into strings. In this paper the basic properties of fair languages are briefly summarized and also extended with respect to previous works [Bre94]: hierarchy, semilinearity, closure, decidability and comparison with the Chomsky hierarchy are dealt with. The family offair languages is however far larger than the regular one; as a novel contribution this paper investigates its subfamilies that are comparable with regular languages. The main result that the regular subfamilies offair languages constitute a proper hierarchy. These subfamilies are then characterized and their properties are explored, showing that they are, in general, more mathematically tractable than fair languages. The conclusion lists comparisons with related works, open problems and research directions.

We settle here two problems concerning the generative power of parallel communicating grammar systems with right-linear components: (1) each linear language can be generated by a non-centralized returning system, (2) the family of languages generated by centifilized returning systems is incomparable with the family of languages generated by non-returning centralized systems. It is also proved that centralized returning systents with right-linear components are strictly more powerful than systems with regular rules in the restricted sense.

Works dealing with grammatical inference of stochastic grammars often evaluate the relative entropy between the model and the true grammar by means of large test sets generated with the true distribution. In this paper, an iterative procedure to compute the relative entropy between two stochastic deterministic regular grammars is proposed.

We introduce a hierarchy of cyclic languages. The kth level of this hierarchy consists of all cyclic languages which are equal to some boolean combination of size k of strongly cyclic languages. We then show how this hierarchy can be characterized by chains of idempotents in monoids. Finally, we give a method to compute an optimal (in the number of terms) decomposition of a cyclic language into strongly cyclic languages.

A loop of a semi-Thue system is a reduction chain where the start word reappears as a factor of the obtained word after a finite number of reduction steps. A rewriting system admitting a loop is clearly nonterminating. The semi-Thue systems consisting of only one rule which admit loops of length 1, 2 or 3 are characterized. Length-1-loops are trivial. 2-loops turn out to have a unique structure, whereas one-rule systems admitting a 3-loop (but no 2-loop) can belong to three structurally different types.

A language X on an alphabet A is unavoidable iff all but finitely many words in A * have a factor in X. In this paper, cuts (which are basically simplifications of languages in terms of avoidability) and innocent language (those which cannot be cut) are defined. Their properties, most of which are related to unavoidable languages, are studied.

Dans cet article, on etudie les proprietes de cloture pour la famille des langages qui satisfont les conditions du «lemme de l'echange» et on compare ces conditions et d'autres conditions d'iteration dans les langages formels

Dans un monoide libre muni de la topologie de groupes finis nous considerons l'ensemble d'egalite de morphismes et nous demontrons qu'il est dense nulle part

In this paper we analyze some intrusion detection strategies proposed in the literature and we show that they represent the various facets of a well known formal languages problem: computing the distance between a string x and a language L . In particular, the main differences among the various approaches adopted for building intrusion detection systems can be reduced to the characteristics of the language L and to the notion of distance adopted. As a further contribution we will also show that from the computational point of view all these strategies are equivalent and they are amenable to efficient parallelization.

Introduction des automates systoliques pour VLSI comme accepteurs avec un grand degre de parallelisme. On concentre l'attention sur les automates d'arbres

Etant donnee une serie formelle en variables non commutatives sur un alphabet fini X, a coefficients dans un corps K, on propose une construction de serie rationnelle approximante au sens de la valuation X-adique, et qui soit de rang minimal

La theorie des codes s'est developpee a la suite des travaux de M.P. Schupzenberger sur les langages formels, les codes apparaissant comme un objet fondamental de la combinatoire du nonoide libre. Construction d'une nouvelle famille de sous-nonoides libres, finement engendres, dont la base est asynchrone et indecomposable par des codes prefixes ou suffixes

Soit M un monoide commutatif infini. Supposons que M possede une presentation finie ayant la propriete de «Church-Rosser». Si M est simplifiable ou si la presentation est speciale, alors M est soit le groupe cyclique libre soit le monoide cyclique libre