Skip to Main content Skip to Navigation
Journal articles

State Complexity of Multiple Catenations

Pascal Caron 1, 2 Jean-Gabriel Luque 1, 2 Bruno Patrou 1, 2
1 CA - LITIS - Equipe Combinatoire et algorithmes
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Abstract : We improve some results relative to the state complexity of the multiple catenations described by Gao and Yu. In particular we nearly divide by 2 the size of the alphabet needed for witnesses. We also give some refinements to the algebraic expression of the state complexity, which is especially complex with this operation. We obtain these results by using peculiar DFAs defined by Brzozowski.
Document type :
Journal articles
Complete list of metadatas

https://hal-normandie-univ.archives-ouvertes.fr/hal-02087862
Contributor : Pascal Caron <>
Submitted on : Tuesday, April 2, 2019 - 1:42:32 PM
Last modification on : Tuesday, July 23, 2019 - 9:11:52 AM

Identifiers

Citation

Pascal Caron, Jean-Gabriel Luque, Bruno Patrou. State Complexity of Multiple Catenations. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2018, 160 (3), pp.255-279. ⟨10.3233/FI-2018-1683⟩. ⟨hal-02087862⟩

Share

Metrics

Record views

39