On the transition reduction problem for finite automata

2013/01/16 by El Houcein El Abdalaoui, el Houcein el Abdalaoui, Mohamed Dahmoune +4
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #cs.FL #math.CO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1301.3751

22 pages, 7 figures, submitted; Keywords: language, automata, reduction, deterministic minimal automaton, state, regular expression, $Z$-partition, $P$-trees

arxiv created 2013/01/16 · openalex publication_date 2013/01/16 · arxiv updated 2013/01/17 · openalex created_date 2019/07/12 · openalex updated_date 2026/07/28

Abstract

We are interested in the problem of transition reduction of nondeterministic automata. We present some results on the reduction of the automata recognizing the language L(E_n) denoted by the regular expression E_n=(1+ε)... (2+ε)... (3+ε)... (n+ε). These results can be used in the general case of the transition reduction problem.

Related

• From Finite Automata to Regular Expressions and Back--A Summary on Descriptional Complexity
• Algebraic Elimination of epsilon-transitions
• From regular expressions to deterministic finite automata: 2^(n)/(2)+√(n)(log n)^Θ(1) states are necessary and sufficient
• Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata
• Real-valued affine automata compute beyond Turing machines