All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 30

Showing per page

D0L sequence equivalence is in P for fixed alphabets

Keijo Ruohonen (2008)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of ℤ -rational sequences.

D0L sequence equivalence is in P for fixed alphabets

Keijo Ruohonen (2007)

RAIRO - Theoretical Informatics and Applications

A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of ℤ -rational sequences.

Decidability of code properties

Henning Fernau, Klaus Reinhardt, Ludwig Staiger (2007)

RAIRO - Theoretical Informatics and Applications

We explore the borderline between decidability and undecidability of the following question: “Let C be a class of codes. Given a machine 𝔐 of type X, is it decidable whether the language L ( 𝔐 ) lies in C or not?” for codes in general, ω-codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.

Deciding inclusion of set constants over infinite non-strict data structures

Manfred Schmidt-Schauss, David Sabel, Marko Schütz (2007)

RAIRO - Theoretical Informatics and Applications

Various static analyses of functional programming languages that permit infinite data structures make use of set constants like Top, Inf, and Bot, denoting all terms, all lists not eventually ending in Nil, and all non-terminating programs, respectively. We use a set language that permits union, constructors and recursive definition of set constants with a greatest fixpoint semantics in the set of all, also infinite, computable trees, where all term constructors are non-strict. This...

Deciding whether a relation defined in Presburger logic can be defined in weaker logics

Christian Choffrut (2008)

RAIRO - Theoretical Informatics and Applications

We consider logics on ℤ and ℕ which are weaker than Presburger arithmetic and we settle the following decision problem: given a k-ary relation on ℤ and ℕ which are first order definable in Presburger arithmetic, are they definable in these weaker logics? These logics, intuitively, are obtained by considering modulo and threshold counting predicates for differences of two variables.

Decimations and sturmian words

Jacques Justin, Giuseppe Pirillo (1997)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Decision problems among the main subfamilies of rational relations

Olivier Carton, Christian Choffrut, Serge Grigorieff (2006)

RAIRO - Theoretical Informatics and Applications

We consider the four families of recognizable, synchronous, deterministic rational and rational subsets of a direct product of free monoids. They form a strict hierarchy and we investigate the following decision problem: given a relation in one of the families, does it belong to a smaller family? We settle the problem entirely when all monoids have a unique generator and fill some gaps in the general case. In particular, adapting a proof of Stearns, we show that it is recursively decidable whether...

Deformed fuzzy automata for the Text Error Correction Problem.

F. Javier Echanobe Arias, José Ramón Garitagoitia, José Ramón González de Mendívil, José Javier Astráin (2000)

Mathware and Soft Computing

A fuzzy method for the text error correction problem is introduced. The method is able to handle insert, delete and substitution errors. Moreover, it uses the measurement level output that an Isolated Character Classifier can provide. The method is based on a Deformed System, in particular, a deformed fuzzy automaton is defined to model the possible errors in the words of the texts. Experimental results show good performance in correcting the three types of errors.

Design of mealy finite-state machines with the transformation of object codes

Alexander Barkalov, Alexander Barkalov (2005)

International Journal of Applied Mathematics and Computer Science

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...

Deterministic blow-ups of minimal NFA's

Galina Jirásková (2006)

RAIRO - Theoretical Informatics and Applications

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...

Currently displaying 1 – 20 of 30

Page 1 Next