Page 1

Displaying 1 – 13 of 13

Showing per page

Implementation of directed acyclic word graph

Miroslav Balík (2002)

Kybernetika

An effective implementation of a Directed Acyclic Word Graph (DAWG) automaton is shown. A DAWG for a text T is a minimal automaton that accepts all substrings of a text T , so it represents a complete index of the text. While all usual implementations of DAWG needed about 30 times larger storage space than was the size of the text, here we show an implementation that decreases this requirement down to four times the size of the text. The method uses a compression of DAWG elements, i. e. vertices,...

Incremental DFA minimisation

Marco Almeida, Nelma Moreira, Rogério Reis (2014)

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

We present a new incremental algorithm for minimising deterministic finite automata. It runs in quadratic time for any practical application and may be halted at any point, returning a partially minimised automaton. Hence, the algorithm may be applied to a given automaton at the same time as it is processing a string for acceptance. We also include some experimental comparative results.

Indécidabilité de la condition IRS

Jean-Michel Autebert, Joffroy Beauquier, Luc Boasson, Michel Latteux (1982)

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

Indexed counter languages

J. Duske, M. Middendorf, R. Parchmann (1992)

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

Iteration of rational transductions

Alain Terlutte, David Simplot (2010)

RAIRO - Theoretical Informatics and Applications

The purpose of this paper is to show connections between iterated length-preserving rational transductions and linear space computations. Hence, we study the smallest family of transductions containing length-preserving rational transductions and closed under union, composition and iteration. We give several characterizations of this class using restricted classes of length-preserving rational transductions, by showing the connections with "context-sensitive transductions" and transductions associated...

Currently displaying 1 – 13 of 13

Page 1