Extremal minimality conditions on automata

Risultato della ricerca: Article

1 Citazione (Scopus)

Abstract

In this paper we investigate the minimality problem of \{DFAs\} by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automaton (uniformly minimal automata), the automata that are minimal for any proper subset F of Q (almost uniformly minimal automata) and the automata that are never minimal, under any assignment of final states (never-minimal automata). More generally, we seek to characterize those families of automata and show that some of them are related to well-known objects in a different context (e.g. multiple-entry automata and Fischer covers of irreducible sofic shifts in Symbolic Dynamics). Next, we study the complexity of the related decision problems and show, in some cases, how to derive a polynomial algorithm. Finally, we pay particular attention to the relationship between the problem to decide if an automaton is never-minimal and the “syntactic monoid problem”.
Lingua originaleEnglish
pagine (da-a)73-84
Numero di pagine12
RivistaTheoretical Computer Science
Volume440–441
Stato di pubblicazionePublished - 2012

Fingerprint

Minimality
Coloring
Syntactics
Automata
Polynomials
Proper subset
Symbolic Dynamics
Polynomial Algorithm
Graph in graph theory
Monoid
Decision problem
Colouring
Assignment
Cover

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

Extremal minimality conditions on automata. / Vaglica, Roberto; Restivo, Antonio.

In: Theoretical Computer Science, Vol. 440–441, 2012, pag. 73-84.

Risultato della ricerca: Article

@article{f1fb7c90e90b4421b96efca58c8a5bdd,
title = "Extremal minimality conditions on automata",
abstract = "In this paper we investigate the minimality problem of \{DFAs\} by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automaton (uniformly minimal automata), the automata that are minimal for any proper subset F of Q (almost uniformly minimal automata) and the automata that are never minimal, under any assignment of final states (never-minimal automata). More generally, we seek to characterize those families of automata and show that some of them are related to well-known objects in a different context (e.g. multiple-entry automata and Fischer covers of irreducible sofic shifts in Symbolic Dynamics). Next, we study the complexity of the related decision problems and show, in some cases, how to derive a polynomial algorithm. Finally, we pay particular attention to the relationship between the problem to decide if an automaton is never-minimal and the “syntactic monoid problem”.",
author = "Roberto Vaglica and Antonio Restivo",
year = "2012",
language = "English",
volume = "440–441",
pages = "73--84",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

TY - JOUR

T1 - Extremal minimality conditions on automata

AU - Vaglica, Roberto

AU - Restivo, Antonio

PY - 2012

Y1 - 2012

N2 - In this paper we investigate the minimality problem of \{DFAs\} by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automaton (uniformly minimal automata), the automata that are minimal for any proper subset F of Q (almost uniformly minimal automata) and the automata that are never minimal, under any assignment of final states (never-minimal automata). More generally, we seek to characterize those families of automata and show that some of them are related to well-known objects in a different context (e.g. multiple-entry automata and Fischer covers of irreducible sofic shifts in Symbolic Dynamics). Next, we study the complexity of the related decision problems and show, in some cases, how to derive a polynomial algorithm. Finally, we pay particular attention to the relationship between the problem to decide if an automaton is never-minimal and the “syntactic monoid problem”.

AB - In this paper we investigate the minimality problem of \{DFAs\} by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automaton (uniformly minimal automata), the automata that are minimal for any proper subset F of Q (almost uniformly minimal automata) and the automata that are never minimal, under any assignment of final states (never-minimal automata). More generally, we seek to characterize those families of automata and show that some of them are related to well-known objects in a different context (e.g. multiple-entry automata and Fischer covers of irreducible sofic shifts in Symbolic Dynamics). Next, we study the complexity of the related decision problems and show, in some cases, how to derive a polynomial algorithm. Finally, we pay particular attention to the relationship between the problem to decide if an automaton is never-minimal and the “syntactic monoid problem”.

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

M3 - Article

VL - 440–441

SP - 73

EP - 84

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -