Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Universal Witnesses for State Complexity of Boolean Operations and Concatenation Combined with Star - MaRDI portal

Deprecated: Use of MediaWiki\Skin\SkinTemplate::injectLegacyMenusIntoPersonalTools was deprecated in Please make sure Skin option menus contains `user-menu` (and possibly `notifications`, `user-interface-preferences`, `user-page`) 1.46. [Called from MediaWiki\Skin\SkinTemplate::getPortletsTemplateData in /var/www/html/w/includes/Skin/SkinTemplate.php at line 691] in /var/www/html/w/includes/Debug/MWDebug.php on line 372

Deprecated: Use of MediaWiki\Skin\BaseTemplate::getPersonalTools was deprecated in 1.46 Call $this->getSkin()->getPersonalToolsForMakeListItem instead (T422975). [Called from Skins\Chameleon\Components\NavbarHorizontal\PersonalTools::getHtml in /var/www/html/w/skins/chameleon/src/Components/NavbarHorizontal/PersonalTools.php at line 66] in /var/www/html/w/includes/Debug/MWDebug.php on line 372

Deprecated: Use of QuickTemplate::(get/html/text/haveData) with parameter `personal_urls` was deprecated in MediaWiki Use content_navigation instead. [Called from MediaWiki\Skin\QuickTemplate::get in /var/www/html/w/includes/Skin/QuickTemplate.php at line 131] in /var/www/html/w/includes/Debug/MWDebug.php on line 372

Universal Witnesses for State Complexity of Boolean Operations and Concatenation Combined with Star

From MaRDI portal
Publication:2843082

DOI10.1007/978-3-642-39310-5_5zbMATH Open1388.68159arXiv1207.1982OpenAlexW1507816177MaRDI QIDQ2843082

Author name not available (Why is that?)

Publication date: 9 August 2013

Published in: (Search for Journal in Brave)

Abstract: We study the state complexity of boolean operations and product (concatenation, catenation) combined with star. We derive tight upper bounds for the symmetric differences and differences of two languages, one or both of which are starred, and for the product of two starred languages. We prove that the previously discovered bounds for the union and the intersection of languages with one or two starred arguments, for the product of two languages one of which is starred, and for the star of the product of two languages can all be met by the recently introduced universal witnesses and their variants.


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



zbMATH Keywords

No records found.


Mathematics Subject Classification ID

No records found.








This page was built for publication: Universal Witnesses for State Complexity of Boolean Operations and Concatenation Combined with Star

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

Retrieved from "https://mardi.schubotz.org/w/index.php?title=Publication:2843082&oldid=15771516"
Powered by MediaWiki