Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata

Jan Daciuk; Denis Maurel; Agata Savary

doi:10.1007/11605157_29

Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata

Abstract

Przedstawione zostają modyfikacje trzech algorytmów przyrostowego i półprzyrostowego tworzenia automatów minimalnych w taki sposób, aby tworzyły automaty pseudominimalne. Istniejący od dawna algorytm Revuza tworzy takie automaty szybciej i zużywając mniej pamięci, ale wymaga kłopotliwego sortowania. Nie nadaje się też do dodawania nowych słów do automatu - ważnej czynności w realizacji dynamicznej doskonałej funkcji mieszającej. Nowe algorytmy nie wymagają sortowania, albo sortowanie jest trywialne.

Citations

1

CrossRef
0

Web of Science
4

Scopus

Authors (3)

Jan Daciuk dr hab. inż.
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology
Denis Maurel
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology
Agata Savary
- Faculty of Electronics, Telecommunications and Informatics
- Gdańsk University of Technology

Cite as

Full text

full text is not available in portal

Keywords

AUTOMATY SKOŃCZONE

Details

Category:: Conference activity
Type:: publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Language:: English
Publication year:: 2005
Bibliographic description:: Daciuk J., Maurel D., Savary A.: Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata// / : , 2005,
DOI:: Digital Object Identifier (open in new tab) 10.1007/11605157_29
Verified by:: Gdańsk University of Technology