At the final stage s, we have d s = m, and the base rows R 1 = D 1 · · · R m = D m are all diagonal. The vector space generated by the accessible states has dimension 2 m , and I ? T (? n) ? F 2 [D 1 · · · D m ] for all n > 0. None of the remaining states [m + 1 · · · n] in A s is accessible, and we can safely reduce the final automaton B = shrink(A s , m) to its final diagonal form, Computing the pivot (alg. 4) requires O(n 2 ) bit operations, and there are m pivots. So, the time complexity is O(mn 2 ). All pivots can be performed in-place, within the O(n 2 ) bits of memory required for representing A. Q.E.D ,
From regular expressions to deterministic automata, Theoretical Computer Science, pp.117-126, 1986. ,
DOI : 10.1016/0304-3975(86)90088-5
URL : https://hal.archives-ouvertes.fr/inria-00075904
Rational Series and Their Languages. EATCS Monograph, 1988. ,
URL : https://hal.archives-ouvertes.fr/hal-00619791
Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys, vol.24, issue.3, pp.293-318, 1992. ,
DOI : 10.1145/136035.136043
Canonical regular expressions and minimal state graphs for definite events, Mathematical theory of Automata, pp.529-561, 1962. ,
Suites alg??briques, automates et substitutions, Bulletin de la Société mathématique de France, vol.79, pp.401-419, 1980. ,
DOI : 10.24033/bsmf.1926
URL : http://archive.numdam.org/article/BSMF_1980__108__401_0.pdf
On the number of distinct languages accepted by finite automata with n states, Journal of Automata, Languages and Combinatorics, vol.7, issue.4, pp.469-486, 2002. ,
On the number of distinct languages accepted by finite automata with n states, Journal of Automata, Languages and Combinatorics, vol.7, pp.469-486, 2002. ,
Automata, Languages, and Machines, volume I, 1974. ,
Matrices de hankel, J. Math pures et appl, vol.53, pp.197-224, 1974. ,
Matrices de hankel, J. Math. pures et appl, vol.53, pp.197-224, 1974. ,
Modern Algebra with Applications, J. Wiley & S, 1976. ,
DOI : 10.1002/0471469882
AN n log n ALGORITHM FOR MINIMIZING STATES IN A FINITE AUTOMATON, The Theory of Machines and Computations, pp.189-196, 1971. ,
DOI : 10.1016/B978-0-12-417750-5.50022-1
The synthesis of sequential switching circuits. The journal of symbolic logic, pp.69-70, 1955. ,
Minimal NFA Problems are Hard, ICALP, pp.629-640, 1991. ,
DOI : 10.1137/0222067
Minimal NFA Problems are Hard, SIAM Journal on Computing, vol.22, issue.6, pp.1117-1141, 1993. ,
DOI : 10.1137/0222067
Coroutines and networks of parallel processes, Proceedings of the IFIP Congress, pp.993-998, 1977. ,
URL : https://hal.archives-ouvertes.fr/inria-00306565
On the state minimalization of nondeterministic finite. automata, IEEE Transactions on Computers, C, vol.19, issue.7, pp.617-627, 1970. ,
Fundamental Algorithms, The Art of Computer Programming, 1997. ,
Sorting and Searching, The Art of Computer Programming, 1998. ,
Enumeration and Backtracking, The Art of Computer Programming, vol.4, 2009. ,
Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory, vol.15, issue.1, pp.122-127, 1969. ,
DOI : 10.1109/TIT.1969.1054260
Weighted automata algorithms -in Handbook of weighted automata, 2009. ,
Gedanken-Experiments on Sequential Machines, The Journal of Symbolic Logic, vol.23, p.60, 1958. ,
DOI : 10.1515/9781400882618-006
Linear automaton transformations, Proceedings of the AMS 9, pp.541-544, 1958. ,
DOI : 10.1090/S0002-9939-1958-0135681-9
Finite Automata and Their Decision Problems, IBM Journal of Research and Development, vol.3, issue.2, pp.114-125, 1959. ,
DOI : 10.1147/rd.32.0114
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.88.4472
On the definition of a family of automata, Information and Control, vol.4, issue.2-3, pp.245-270, 1961. ,
DOI : 10.1016/S0019-9958(61)80020-X
On the definition of a family of automata, Information and Control, vol.4, issue.2-3, pp.245-270, 1961. ,
DOI : 10.1016/S0019-9958(61)80020-X
Bideterministic automata and minimal representations of regular languages, CIAA, pp.61-71, 2003. ,
Succinct Descriptions of Regular Languages with Binary ???-NFAs, CIAA, pp.72-82, 2003. ,
DOI : 10.1007/3-540-45089-0_8
On binary <mml:math altimg="si1.gif" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mo>???</mml:mo></mml:math>-NFAs and succinct descriptions of regular languages, Theoretical Computer Science, vol.328, issue.1-2, pp.161-170, 2004. ,
DOI : 10.1016/j.tcs.2004.07.012
Minimization of unary symmetric difference nfas, Proc. of SAICSIT, pp.125-134, 2004. ,
Finite circuits are characterized by 2-algebraic truth-tables, Advances in Computing Science -ASIAN 2000, pp.1-12, 1961. ,
Digital Algebra and Circuits, pp.733-746 ,
DOI : 10.1007/978-3-540-39910-0_31
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.2652
Essays Dedicated to Zohar Manna on the Occasion of his 64th Birthday, 2004. ,
Combining two algorithms by brzozowski, Proceedings of the Fifth International Conference on Implementing Automata, 2001. ,
DOI : 10.1007/3-540-44674-5_27
URL : http://repository.tue.nl/623893