Universal witnesses for state complexity of basic operations combined with reversal

DOI10.1007/978-3-642-39274-0_8MaRDI QIDQ5327484zbMATH OpenOpenAlexFDO

Authors David Liu, Janusz Brzozowski

Publication date 7 August 2013

Published in Implementation and Application of Automata (Search for Journal in Brave)

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

zbMATH Keywords

regular languagebasic operationstate complexityreversalBoolean operationuniversal witness

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We study the state complexity of boolean operations, concatenation and star with one or two of the argument languages reversed. We derive tight upper bounds for the symmetric differences and differences of such languages. We prove that the previously discovered bounds for union, intersection, concatenation and star of such languages can all be met by the recently introduced universal witnesses and their variants.

Recommendations

• Universal witnesses for state complexity of Boolean operations and concatenation combined with star
• State complexity of basic language operations combined with reversal
• State complexity of combined operations with union, intersection, star and reversal
• State complexity of four combined operations composed of union, intersection, star and reversal
• State complexity of catenation combined with a Boolean operation: a unified approach

Cited in

(2)

• Universal witnesses for state complexity of Boolean operations and concatenation combined with star
• Descriptional complexity of regular languages

This page was built for publication: Universal witnesses for state complexity of basic operations combined with reversal

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