A Family of Algorithms for Non Deterministic Regular Languages Inference | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Family of Algorithms for Non Deterministic Regular Languages Inference

  • Conference paper
Implementation and Application of Automata (CIAA 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4094))

Included in the following conference series:

  • 439 Accesses

Abstract

We present in this paper a new family of algorithms for regular languages inference from complete presentation.

Every algorithm of this family, on input of the sets of words (D  + ,D −), obtains for every x in D  +  at least a non deterministic finite automaton (NFA) which accepts x and is consistent with D −. This automaton is, besides, irreducible in the sense that any further merging of states accepts words of D −. The output of the algorithm is a NFA which consists of the collection of NFAs associated to each word of D  + . Every algorithm of the family converges to a automaton for the target language.

We also present the experiments done to compare one of the algorithms of the family with two other well known algorithms for the same task. The results obtained by our algorithm are better, both in error rate as in the size of the output.

Work partially supported by Spanish CICYT under TIC2003-09319-C03-02.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Arnold, A., Dicky, A., Nivat, M.: A note about minimal non-deterministic automata. Bull. EATCS 47, 166–169 (1970)

    Google Scholar 

  2. Carrez, C.: On the minimalization of non-deterministic automata. Laboratoire de Calcul de la Faculté des Sciences de L’Université de Lille (1970)

    Google Scholar 

  3. Denis, F., Lemay, A., Terlutte, A.: Learning regular languages using RFSAs. Theoretical Computer Science 313(2), 267–294 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  4. García, P., Vazquez de Parga, M.: A Note about mergible states in large NFA. Bull. of the EATCS 87, 181–184 (2005)

    MATH  Google Scholar 

  5. Gold, E.M.: Language identification in the limit. Information and Control 10, 447–474 (1967)

    Article  MATH  Google Scholar 

  6. Gold, E.M.: Complexity of Automaton Identification from Given Data. Information and Control 37, 302–320 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  7. Lombardy, S.: Approche structurelle de quelques problémes de la théorie des automates. Ph.D. Thesis, Ecole N.S. des Télécomunications (2001)

    Google Scholar 

  8. Oncina, J., García, P.: Inferring Regular Languages in Polynomial Updated Time. In: de la Blanca, P., Sanfeliú, Vidal (eds.) Pattern Recognition and Image Analysis. World Scientific, Singapore (1992)

    Google Scholar 

  9. Polák, L.: Minimalizations of NFA using the universal automaton. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol. 3317, pp. 325–326. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Sistemas informáticos y Computación, Universidad Politécnica de Valencia, Camino de Vera s/n, 46022, Valencia, Spain

    Manuel Vázquez de Parga, Pedro García & José Ruiz

Authors
  1. Manuel Vázquez de Parga
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pedro García
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. José Ruiz
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of California, Santa Barbara

    Oscar H. Ibarra

  2. Dept. of Computer Science, Kainan University, Taoyuan, Taiwan, R.O.C.

    Hsu-Chun Yen

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

de Parga, M.V., García, P., Ruiz, J. (2006). A Family of Algorithms for Non Deterministic Regular Languages Inference. In: Ibarra, O.H., Yen, HC. (eds) Implementation and Application of Automata. CIAA 2006. Lecture Notes in Computer Science, vol 4094. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11812128_25

Download citation

  • DOI: https://doi.org/10.1007/11812128_25

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-37213-4

  • Online ISBN: 978-3-540-37214-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation