A bound for the -equivalence problem of polynomial D0L systems
We give a bound for the -equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.
A bound for the ω-equivalence problem of polynomial D0L systems
We give a bound for the ω-equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.
A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
We show that the termination of Mohri's algorithm is decidable for polynomially ambiguous weighted finite automata over the tropical semiring which gives a partial answer to a question by Mohri [29]. The proof relies on an improvement of the notion of the twins property and a Burnside type characterization for the finiteness of the set of states produced by Mohri's algorithm.
A cellular automaton model of brain tumor treatment and resistance.
A cellular automaton on a torus.
A characterization of harmonic languages
A Characterization of Multidimensional -Automatic Sequences
An infinite word is -automatic if, for all , its st letter is the output of a deterministic automaton fed with the representation of in the considered numeration system . In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for , we state that a multidimensional infinite word over a finite alphabet is -automatic for some abstract numeration...
A characterization of poly-slender context-free languages
A characterization of poly-slender context-free languages
For a non-negative integer k, we say that a language L is k-poly-slender if the number of words of length n in L is of order . We give a precise characterization of the k-poly-slender context-free languages. The well-known characterization of the k-poly-slender regular languages is an immediate consequence of ours.
A characterization of rational star languages generated by strong codes.
A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
A classification of rational languages by semilattice-ordered monoids
We prove here an Eilenberg type theorem: the so-called conjunctive varieties of rational languages correspond to the pseudovarieties of finite semilattice-ordered monoids. Taking complements of members of a conjunctive variety of languages we get a so-called disjunctive variety. We present here a non-trivial example of such a variety together with an equational characterization of the corresponding pseudovariety.
A coalgebraic semantics of subtyping
Coalgebras have been proposed as formal basis for the semantics of objects in the sense of object-oriented programming. This paper shows that this semantics provides a smooth interpretation for subtyping, a central notion in object-oriented programming. We show that different characterisations of behavioural subtyping found in the literature can conveniently be expressed in coalgebraic terms. We also investigate the subtle difference between behavioural subtyping and refinement.
A Coalgebraic Semantics of Subtyping
Coalgebras have been proposed as formal basis for the semantics of objects in the sense of object-oriented programming. This paper shows that this semantics provides a smooth interpretation for subtyping, a central notion in object-oriented programming. We show that different characterisations of behavioural subtyping found in the literature can conveniently be expressed in coalgebraic terms. We also investigate the subtle difference between behavioural subtyping and refinement.
A coalgebraic view on reachability
Coalgebras for an endofunctor provide a category theoretic framework for modeling a wide range of state-based systems of various types. We provide an iterative construction of the reachable part of a given pointed coalgebra that is inspired by and resembles the standard breadth-first search procedure to compute the reachable part of a graph. We also study coalgebras in Kleisli categories: for a functor extending a functor on the base category, we show that the reachable part of a given pointed coalgebra...
A coin tossing algorithm for counting large numbers of events
A combinatorial theorem on -power-free words and an application to semigroups
A comparison of multiobjective evolutionary algorithms.
A complete characterization of primitive recursive intensional behaviours
We give a complete characterization of the class of functions that are the intensional behaviours of primitive recursive (PR) algorithms. This class is the set of primitive recursive functions that have a null basic case of recursion. This result is obtained using the property of ultimate unarity and a geometrical approach of sequential functions on N the set of positive integers.
A completeness theorem in the modal logic of programs