State complexity of multiple catenations

DOI10.3233/FI-2018-1683MaRDI QIDQ3174746zbMATH OpenOpenAlexWikidataFDO

Authors Pascal Caron, Bruno Patrou, Jean-Gabriel Luque

Publication date 18 July 2018

Published in Fundamenta Informaticae (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.

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

Cited in

(5)

• The number of multistate nested canalyzing functions
• scientific article; zbMATH DE number 7453075 (Why is no real title available?)
• State complexity of pseudocatenation
• New tools for state complexity
• Operational state complexity revisited: the contribution of monsters and modifiers

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)