Infinite words and biprefix codes

Let A be an alphabet and ƒ be a right infinite word on A. If ƒ is not ultimately periodic then there exists an infinite set {v_ii0} of (finite) words on A such that ƒ=v₀v₁…v_i…, {v_ii1} is a biprefix code and v_i≠v_j for positive integers i≠j.     

Complementing deterministic tree-walking automata

We consider various kinds of deterministic tree-walking automata, with and without pebbles, over ranked and unranked trees. For each such kind of automata we show that there is an equivalent one which never loops. The main consequence of this result is the closure under complementation of the various types of automata we consider with a focus on the number of pebbles used in order to complement the automata.     

Strategical languages of infinite words

We deal in this paper with strategical languages of infinite words, that is those generated by a nondeterministic strategy in the sense of game theory. We first show the existence of a minimal strategy for such languages, for which we give an explicit expression. Then we characterize the family of strategical languages as that of closed ones, in the topological space of infinite words. Finally, we give a definition of a Nash equilibrium for such languages, that we illustrate with a famous example.     

A lower bound on the size of ε-free NFA corresponding to a regular expression

Hromkovic? et al. showed how to transform a regular expression of size n into an ε-free nondeterministic finite automaton (which defines the same language as the expression) with O(n) states and O(nlog²(n)) transitions. They also established a lower bound on the number of transitions. We improve the lower bound to .     

Some characterizations of Parikh matrix equivalent binary words

We state different characterizations of pair of words having the same Parikh matrix.     

Square-free partial words

We say that a partial word w over an alphabet A is square-free if every factor xx^′ of w such that x and x^′ are compatible is either of the form ?a or a? where ? is a hole and a∈A. We prove that there exist uncountably many square-free partial words over a ternary alphabet with an infinite number of holes.     

A Kleene theorem for splitable signals

In this paper, we consider timed automata for piecewise constant signals and prove that they recognize exactly the languages denoted by signal regular expressions with intersection and renaming. The main differences from the usual timed automata are: time elapses on transitions (passing through a state is instantaneous), signals may be split on a run on an automaton and constraints on transitions correspond to unions of open intervals but should be satisfied on closed intervals. This makes exact rendez-vous impossible. The paper stresses on the similarities and differences from the usual model.     

More restrictive Gray codes for necklaces and Lyndon words

In the last years, the order induced by the Binary Reflected Gray Code or its generalizations shown an increasing interest. In this note we show that the BRGC order induces a cyclic 2-Gray code on the set of binary necklaces and Lyndon words and a cyclic 3-Gray code on the unordered counterparts. This is an improvement and a generalization to unlabeled words of the result in [V. Vajnovszki, Gray code order for Lyndon words, Discrete Math. Theoret. Comput. Sci. 9 (2) (2007) 145-152; M. Weston, V. Vajnovszki, Gray codes for necklaces and Lyndon words of arbitrary base, Pure Mathematics and Applications/Algebra and Theoretical Computer Science, in press]; however an algorithmic implementation of our Gray codes remains an open problem.     

Doubly-Constrained LCS and Hybrid-Constrained LCS problems revisited

We revisit two recently studied variants of the classic Longest Common Subsequence (LCS) problem, namely, the Doubly-Constrained LCS (DC-LCS) and Hybrid-Constrained LCS (HC-LCS) problems. We present finite automata based algorithms for both problems.     

E<Emphasis Type="SmallCaps">ssence</Emphasis>: A constraint language for specifying combinatorial problems

Essence is a formal language for specifying combinatorial problems in a manner similar to natural rigorous specifications that use a mixture of natural language and discrete mathematics. Essence provides a high level of abstraction, much of which is the consequence of the provision of decision variables whose values can be combinatorial objects, such as tuples, sets, multisets, relations, partitions and functions. Essence also allows these combinatorial objects to be nested to arbitrary depth, providing for example sets of partitions, sets of sets of partitions, and so forth. Therefore, a problem that requires finding a complex combinatorial object can be specified directly by using a decision variable whose type is precisely that combinatorial object.     

A structure theorem for maximum internal matchings in graphs

A counterpart of the Gallai-Edmonds Structure Theorem is proved for matchings that are not required to cover the external vertices of graphs. The appropriate counterpart of Tutte's Theorem is derived from this result for the existence of perfect internal matchings in graphs.     

A counterexample to a conjecture concerning concatenation hierarchies

We give a counterexample to the conjecture which was originally formulated by Straubing in 1986 concerning a certain algebraic characterization of regular languages of level 2 in the Straubing-Thérien concatenation hierarchy of star-free languages.     

On a language without star

We solve a problem raised by Boasson [5] concerning the language B^*₁ = s{;xⁿ(y⁺x⁺)^*yⁿ vb; n ? 1s};^*. We prove that t he rational cone generated by B^*₁ which is closed under product but not under the star operation [5] does not contain any non-rational AFL.     

P-hardness of the emptiness problem for visibly pushdown languages

Visibly pushdown languages form a subclass of the context-free languages which is appealing because of its nice algorithmic and closure properties. Here we show that the emptiness problem for this class is not any easier than the emptiness problem for context-free languages, namely hard for deterministic polynomial time. The proof consists of a reduction from the alternating graph reachability problem.