Descriptional complexity measures of context-free languages
Design of mealy finite-state machines with the transformation of object codes
An optimization method of the logic circuit of a Mealy finite-state machine is proposed. It is based on the transformation of object codes. The objects of the Mealy FSM are internal states and sets of microoperations. The main idea is to express the states as some functions of sets of microoperations (internal states) and tags. The application of this method is connected with the use of a special code converter in the logic circuit of an FSM. An example of application is given. The effectiveness...
Detecting the morphic images of a word : improving the general algorithm
Detection of deadlocks and traps in Petri nets by means of Thelen's prime implicant method
A new method of detecting deadlocks and traps in Petri nets is presented. Deadlocks and traps in Petri nets can be represented by the roots of special equations in CNF form. Such equations can be solved by using the search tree algorithm proposed by Thelen. In order to decrease the tree size and to accelerate the computations, some heuristics for Thelen's method are presented.
Détermination de la représentation standard d'une série reconnaissable
Deterministic blow-ups of minimal NFA's
The paper treats the question whether there always exists a minimal nondeterministic finite automaton of n states whose equivalent minimal deterministic finite automaton has α states for any integers n and α with n ≤ α ≤ 2n. Partial answers to this question were given by Iwama, Kambayashi, and Takaki (2000) and by Iwama, Matsuura, and Paterson (2003). In the present paper, the question is completely solved by presenting appropriate automata for all values of n and α. However, in order to...
Deux méthodes et quatre programmes automatiques de calcul de la fiabilité des circuits
Deux propriétés combinatoires du langage de Lukasiewicz
Deux remarques sur un théorème de S. Eilenberg
Diagonalization in proof complexity
We study diagonalization in the context of implicit proofs of [10]. We prove that at least one of the following three conjectures is true: ∙ There is a function f: 0,1* → 0,1 computable in that has circuit complexity . ∙ ≠ co . ∙ There is no p-optimal propositional proof system. We note that a variant of the statement (either ≠ co or ∩ co contains a function hard on average) seems to have a bearing on the existence of good proof complexity generators. In particular, we prove that if a minor variant...
Diagrammes de Penrose et réécriture en dimension
Dicovering spaces.
Die Berechnungskomplexität von elementarsymmetrischen Funkit
Die mit Nestedstackautomaten berechenbaren Funktionen sind elementar.
Different time solutions for the firing squad synchronization problem on basic grid networks
We present several solutions to the Firing Squad Synchronization Problem on grid networks of different shapes. The nodes are finite state processors that work in unison with other processors and in synchronized discrete steps. The networks we deal with are: the line, the ring and the square. For all of these models we consider one- and two-way communication modes and we also constrain the quantity of information that adjacent processors can exchange at each step. We first present synchronization...
Digits and continuants in euclidean algorithms. Ergodic versus tauberian theorems
We obtain new results regarding the precise average-case analysis of the main quantities that intervene in algorithms of a broad Euclidean type. We develop a general framework for the analysis of such algorithms, where the average-case complexity of an algorithm is related to the analytic behaviour in the complex plane of the set of elementary transformations determined by the algorithms. The methods rely on properties of transfer operators suitably adapted from dynamical systems theory and provide...
Dijkstra's Interpretation of the Approach to Solving a Problem of Program Correctness
Directable automata and directly subdefinite events
Directable automata and their generalizations: A survey.
Disjunction in modal description logics.