Universal automata and NFA learning

Pedro García; Manuel Vázquez de Parga; Gloria I. Álvarez; José Ruiz

doi:10.1016/j.tcs.2008.05.017

Universal automata and NFA learning

Pedro García
, Manuel Vázquez de Parga
, Gloria I. Álvarez
, José Ruiz

Polytechnic University of Valencia

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

Abstract

The aim of this paper is to develop a new algorithm that, with a complete sample as input, identifies the family of regular languages by means of nondeterministic finite automata. It is a state-merging algorithm. One of its main features is that the convergence (which is proved) is achieved independently from the order in which the states are merged, that is, the merging of states may be done "randomly".

Original language	English
Pages (from-to)	192-202
Number of pages	11
Journal	Theoretical Computer Science
Volume	407
Issue number	1-3
DOIs	https://doi.org/10.1016/j.tcs.2008.05.017
State	Published - 06 Nov 2008

Keywords

Finite automata
Grammatical inference
Universal automaton

Access to Document

10.1016/j.tcs.2008.05.017

Cite this

@article{51afffb27c3b48948725ab1679fbc8ca,

title = "Universal automata and NFA learning",

abstract = "The aim of this paper is to develop a new algorithm that, with a complete sample as input, identifies the family of regular languages by means of nondeterministic finite automata. It is a state-merging algorithm. One of its main features is that the convergence (which is proved) is achieved independently from the order in which the states are merged, that is, the merging of states may be done {"}randomly{"}.",

keywords = "Finite automata, Grammatical inference, Universal automaton",

author = "Pedro Garc{\'i}a and \{V{\'a}zquez de Parga\}, Manuel and {\'A}lvarez, \{Gloria I.\} and Jos{\'e} Ruiz",

note = "Funding Information: Work partially supported by Spanish Ministry of Education and Science research project TIN2007-60769. Corresponding author. E-mail addresses: [email protected] (P. Garc{\'i}a), [email protected] (M. V{\'a}zquez de Parga), [email protected] (G.I. {\'A}lvarez), [email protected] (J. Ruiz).",

year = "2008",

month = nov,

day = "6",

doi = "10.1016/j.tcs.2008.05.017",

language = "English",

volume = "407",

pages = "192--202",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Universal automata and NFA learning

AU - García, Pedro

AU - Vázquez de Parga, Manuel

AU - Álvarez, Gloria I.

AU - Ruiz, José

N1 - Funding Information: Work partially supported by Spanish Ministry of Education and Science research project TIN2007-60769. Corresponding author. E-mail addresses: [email protected] (P. García), [email protected] (M. Vázquez de Parga), [email protected] (G.I. Álvarez), [email protected] (J. Ruiz).

PY - 2008/11/6

Y1 - 2008/11/6

N2 - The aim of this paper is to develop a new algorithm that, with a complete sample as input, identifies the family of regular languages by means of nondeterministic finite automata. It is a state-merging algorithm. One of its main features is that the convergence (which is proved) is achieved independently from the order in which the states are merged, that is, the merging of states may be done "randomly".

AB - The aim of this paper is to develop a new algorithm that, with a complete sample as input, identifies the family of regular languages by means of nondeterministic finite automata. It is a state-merging algorithm. One of its main features is that the convergence (which is proved) is achieved independently from the order in which the states are merged, that is, the merging of states may be done "randomly".

KW - Finite automata

KW - Grammatical inference

KW - Universal automaton

UR - https://www.scopus.com/pages/publications/50249162059

U2 - 10.1016/j.tcs.2008.05.017

DO - 10.1016/j.tcs.2008.05.017

M3 - Article

AN - SCOPUS:50249162059

SN - 0304-3975

VL - 407

SP - 192

EP - 202

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-3

ER -

Universal automata and NFA learning

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this