Cited By
View all- Gruber HHolzer MJakobi S(2017)More on deterministic and nondeterministic finite cover automataTheoretical Computer Science10.1016/j.tcs.2016.10.006679:C(18-30)Online publication date: 30-May-2017
The number of similarity relations and the number of minimal deterministic finite cover automata
Pages 67 - 76
Abstract
Finite Deterministic Cover Automata (DFCA) can be obtained from Deterministic Finite Automata (DFA) using the similarity relation. Since the similarity relation is not an equivalence relation, the minimal DFCA for a finite language is usually not unique. We count the number of minimal DFCA that can be obtained from a given minimal DFA with n states by merging the similar states in the given DFA. We compute an upper bound for this number and prove that in the worst case (for a non-unary alphabet) it is ⌈4n-9+√8n+1/8⌉!/(2⌈4n-9+√8n+1/8⌉ - n + 1)! We prove that this upper bound is reached, i.e. for any given positive integer n we find a minimal DFA with n states, which has the number of minimal DFCA obtained by merging similar states equal to this maximum.
References
[1]
C. Câmpeanu, N. Sântean and S. Yu, "Minimal Cover-Automata for Finite Languages", Proceedings of the Third International Workshop on Implementing Automata WIA'98 (1998), 32-42 and TCS vol 267 (2001), 3-16.
[2]
C. Dwork and L. Stockmeyer, "A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata", SIAM Journal on Computing, vol.19 (1990), 1011-1023.
[3]
J. E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation Addison-Wesley, (1979).
[4]
J. Kaneps, R. Frievalds, "Running Time to Recognize Non-Regular Languages by 2-Way Probabilistic Automata", in ICALP'91, LNCS, Springer-Verlag, New-York/Berlin (1991) vol 510, 174-185.
[5]
A. Paun, N. Sântean and Sheng Yu, "An O(n2) algorithm for Minimal Cover-Automata for Finite Languages", Proceedings of the 5th International Conference on Implementation and Application of Automata CIAA'00 (2000), 243-251.
[6]
N. Sântean, Towards a Minimal Representation for Finite Languages: Theory and Practice, MSc Thesis, Department of Computer Science, The University of Western Ontario, (2000).
[7]
J. M. Champarnaud and D. Maurel, Automata Implementation, Proceedings of Third International Workshop on Implementing Automata, LNCS 1660, Springer, (1999).
[8]
A. Salomaa, Formal Languages Academic Press, (1973).
[9]
S. Yu, "Regular languages", in Handbook of Formal Languages, Vol I, eds. G. Rozenberg and A. Salomaa, Springer-Verlag, (1997), 41-110.
[10]
D. Wood and S. Yu, Automata Implementation, Proceedings of Second International Workshop on Implementing Automata, LNCS 1436, Springer, (1998).
- The number of similarity relations and the number of minimal deterministic finite cover automata
Recommendations
Minimal cover-automata for finite languages
A cover-automaton A of a finite language L Σ is a finite deterministic automaton (DFA) that accepts all words in L and possibly other words that are longer than any word in L. A minimal deterministic finite cover automaton (DFCA) of a finite language L ...
Incremental construction of minimal deterministic finite cover automata
Implementation and application of automataWe present a fast incremental algorithm for constructing minimal Deterministic Finite Cover Automata (DFCA) for a given language. Since it was shown that the minimal DFCA for a language L has less states than the minimal Deterministic Finite Automata (...
More on deterministic and nondeterministic finite cover automata
Finite languages are an important sub-regular language family, which were intensively studied during the last two decades in particular from a descriptional complexity perspective. An important contribution to the theory of finite languages are the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
- EATCS: European Association for Theoretical Computer Science
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 03 July 2002
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
Cited By
View all- Gruber HHolzer MJakobi S(2017)More on deterministic and nondeterministic finite cover automataTheoretical Computer Science10.1016/j.tcs.2016.10.006679:C(18-30)Online publication date: 30-May-2017
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in