A graph theoretic approach to automata minimality

Risultato della ricerca: Article

4 Citazioni (Scopus)

Abstract

The paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F . We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.
Lingua originaleEnglish
pagine (da-a)282-291
Numero di pagine10
RivistaTheoretical Computer Science
Volume429
Stato di pubblicazionePublished - 2012

Fingerprint

Minimality
Automata
Graph in graph theory
Cardinality
Term

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

@article{c3c3c7ef3337433b959d4948080a257f,
title = "A graph theoretic approach to automata minimality",
abstract = "The paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F . We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.",
author = "Antonio Restivo and Roberto Vaglica",
year = "2012",
language = "English",
volume = "429",
pages = "282--291",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

TY - JOUR

T1 - A graph theoretic approach to automata minimality

AU - Restivo, Antonio

AU - Vaglica, Roberto

PY - 2012

Y1 - 2012

N2 - The paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F . We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.

AB - The paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F . We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.

UR - http://hdl.handle.net/10447/73706

M3 - Article

VL - 429

SP - 282

EP - 291

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -