Universal witnesses for state complexity of basic operations combined with reversal
From MaRDI portal
Publication:5327484
DOI10.1007/978-3-642-39274-0_8zbMATH Open1298.68124arXiv1207.0535OpenAlexW1708004621MaRDI QIDQ5327484FDOQ5327484
Authors: David Liu, Janusz Brzozowski 
Publication date: 7 August 2013
Published in: Implementation and Application of Automata (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1207.0535
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)
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)
