State complexity of multiple catenations

DOI10.3233/FI-2018-1683zbMATH Open1393.68089arXiv1607.04031OpenAlexW2963188010WikidataQ129736881 ScholiaQ129736881MaRDI QIDQ3174746FDOQ3174746

Jean-Gabriel Luque, Bruno Patrou, Pascal Caron

Publication date: 18 July 2018

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Abstract: We improve some results relative to the state complexity of the multiple catenation 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.

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

Recommendations

• The state complexities of some basic operations on regular languages
• The Complexity of Languages Resulting from the Concatenation Operation
• State complexity of catenation combined with a Boolean operation: a unified approach
• State complexity of two combined operations: catenation-union and catenation-intersection
• State complexity of catenation combined with union and intersection

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (5)

• Title not available (Why is that?)
• Operational state complexity revisited: the contribution of monsters and modifiers
• State complexity of pseudocatenation
• The number of multistate nested canalyzing functions
• Title not available (Why is that?)

This page was built for publication: State complexity of multiple catenations

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