Displaying similar documents to “Hopcroft's algorithm and tree-like automata”

Hopcroft's algorithm and tree-like automata

G. Castiglione, A. Restivo, M. Sciortino (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard...

Minimal 2-dominating sets in trees

Marcin Krzywkowski (2013)

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

Similarity:

We provide an algorithm for listing all minimal 2-dominating sets of a tree of order in time 𝒪(1.3248). This implies that every tree has at most 1.3248 minimal 2-dominating sets. We also show that this bound is tight.

The triangles method to build -trees from incomplete distance matrices

Alain Guénoche, Bruno Leclerc (2010)

RAIRO - Operations Research

Similarity:

A method to infer -trees (valued trees having as set of leaves) from incomplete distance arrays (where some entries are uncertain or unknown) is described. It allows us to build an unrooted tree using only 2-3 distance values between the elements of , if they fulfill some explicit conditions. This construction is based on the mapping between -tree and a weighted generalized 2-tree spanning .

Distance desert automata and the star height problem

Daniel Kirsten (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

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