On the Transition Reduction Problem for Finite Automata

DOI10.3233/FI-2014-1033MaRDI QIDQ2934875zbMATHOpenAlexFDO

Authors Mohamed Dahmoune, Djelloul Ziadi, El Houcein El Abdalaoui

Publication date 22 December 2014

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.3751

zbMATH Keywords

treeminimizationautomatareductiontransition

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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+varepsilon)\mathrm{...}(2+varepsilon)\mathrm{...}(3+varepsilon)\mathrm{...}(n+varepsilon)$. These results can be used in the general case of the transition reduction problem.

Recommendations

• scientific article; zbMATH DE number 4166871
• scientific article; zbMATH DE number 4108165
• Behaviour, reduction and minimization of finite \({\mathbb{L}}\)-automata
• scientific article; zbMATH DE number 3866601
• Automata for reduction properties solving
• Equivalence, reduction and minimization of finite automata over semirings
• scientific article; zbMATH DE number 459363
• scientific article; zbMATH DE number 3273202
• Reduction of a kind of finite-state automata over unitary semirings
• scientific article; zbMATH DE number 6300100

Cited in

(6)

• scientific article; zbMATH DE number 3866601 (Why is no real title available?)
• Implementation and Application of Automata
• scientific article; zbMATH DE number 7561353 (Why is no real title available?)
• Implementation and Application of Automata
• Compression of finite-state automata through failure transitions
• Lower bounds for the transition complexity of NFAs

This page was built for publication: On the Transition Reduction Problem for Finite Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934875)