Efficient Equivalence and Minimization for Non Deterministic Xor Automata

Jean Vuillemin 1, * Nicolas Gama 2
* Auteur correspondant
2 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : A word w in a regular language L is or-accepted by a non-deterministic finite or-automaton A if there exists a path along w from some initial state to some final state in A. The same word w is xor-accepted by the same non-deterministic finite xor-automaton A if the number of accepting pathes is odd. In the deterministic case, accepting pathes are unique and both definitions coincide. No polynomial time algorithm is known to minimize NFAs or to compute their equivalence. By contrast, we present a cubic time algorithm to reduce a xor-automaton to a minimal form M = MXA(A), within the least possible number of states. It is a finite strong normal form and automata equivalence is efficiently decided through reduction to the SNF.
Type de document :
Rapport
[Research Report] 2010, pp.25
Liste complète des métadonnées

Littérature citée [36 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00487031
Contributeur : Nicolas Gama <>
Soumis le : jeudi 27 mai 2010 - 16:57:20
Dernière modification le : jeudi 12 avril 2018 - 10:46:09
Document(s) archivé(s) le : jeudi 16 septembre 2010 - 15:27:51

Fichier

MXA.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00487031, version 1

Collections

Citation

Jean Vuillemin, Nicolas Gama. Efficient Equivalence and Minimization for Non Deterministic Xor Automata. [Research Report] 2010, pp.25. 〈inria-00487031〉

Partager

Métriques

Consultations de la notice

334

Téléchargements de fichiers

329