Abstract | ||
---|---|---|
Pseudo-minimal automata ([1],[2]) are minimal acyclic automata that have a proper element (a transition or a state) for each word belonging to the language of the automaton. That proper element is not shared with any other word, and it can be used for implementing a function on words belonging to the language. For instance, dynamic perfect hashing (e.g. a mapping from n unique words to n consecutive numbers, such that addition of new elements does not change the order of the previous elements) can be implemented using a pseudo-minimal automaton ([3]). |
Year | DOI | Venue |
---|---|---|
2005 | 10.1007/11605157_29 | CIAA |
Keywords | Field | DocType |
semi-incremental construction,pseudo-minimal automaton,new element,minimal acyclic automaton,consecutive number,n unique word,previous element,proper element | Discrete mathematics,Automata theory,Deterministic automaton,Nondeterministic finite automaton,Continuous spatial automaton,Mobile automaton,Nested word,Theoretical computer science,Timed automaton,Mathematics,ω-automaton | Conference |
Volume | ISSN | ISBN |
3845 | 0302-9743 | 3-540-31023-1 |
Citations | PageRank | References |
3 | 0.42 | 5 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jan Daciuk | 1 | 156 | 14.83 |
Denis Maurel | 2 | 84 | 20.72 |
Agata Savary | 3 | 92 | 19.55 |