Disjunctive languages and compatible orders
Disjunktive Teilmengen inverser Halbgruppen
Distance desert automata and the star height problem
We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in space whether the language accepted by an -state non-deterministic automaton is of a star height less than a given integer (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity bound...
Distance desert automata and the star height problem
We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity...
Distinguishing subsets in lattices
Division in logspace-uniform
Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform .
Division in logspace-uniform NC1
Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., NC1 circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform NC1.
Domain mu-calculus
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....
Domain mu-calculus
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...
Domain-free -calculus
Domain-Free λµ-Calculus
We introduce a domain-free λµ-calculus of call-by-value as a short-hand for the second order Church-style. Our motivation comes from the observation that in Curry-style polymorphic calculi, control operators such as callcc-operators cannot, in general, handle correctly the terms placed on the control operator's left, so that the Curry-style system can fail to prove the subject reduction property. Following the continuation semantics, we also discuss the notion of values in classical system,...
Drawing graphs on two and three lines.
Drunken man infinite words complexity
In this article, we study the complexity of drunken man infinite words. We show that these infinite words, generated by a deterministic and complete countable automaton, or equivalently generated by a substitution over a countable alphabet of constant length, have complexity functions equivalent to n(log2n)2 when n goes to infinity.
Dynamic overloading with copy semantics in object-oriented languages: a formal account
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.
Dynamic Point Location in Arrangements of Hyperplanes.
Dynamic programming for reduced NFAs for approximate string and sequence matching
searching for all occurrences of a pattern (string or sequence) in some text, where the pattern can occur with some limited number of errors given by edit distance. Several methods were designed for the approximate string matching that simulate nondeterministic finite automata (NFA) constructed for this problem. This paper presents reduced NFAs for the approximate string matching usable in case, when we are interested only in occurrences having edit distance less than or equal to a given integer,...
Dynamic properties of cellular neural networks.
Dynamical directions in numeration
This survey aims at giving a consistent presentation of numeration from a dynamical viewpoint: we focus on numeration systems, their associated compactification, and dynamical systems that can be naturally defined on them. The exposition is unified by the fibred numeration system concept. Many examples are discussed. Various numerations on rational integers, real or complex numbers are presented with special attention paid to -numeration and its generalisations, abstract numeration systems and...
Dynamics in binary neural networks with a finite number of patterns. I: General picture of the asynchronous zero temperature dynamics.
Each regular code is included in a maximal regular code