Operational state complexity revisited: the contribution of monsters and modifiers

DOI10.1007/978-3-031-34326-1_1MaRDI QIDQ6175083zbMATH OpenOpenAlexFDO

Authors Pascal Caron, Jean-Gabriel Luque, Bruno Patrou

Publication date 17 August 2023

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-34326-1_1

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 2068872 (Why is no real title available?)
• scientific article; zbMATH DE number 7453083 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• A Study of a Simple Class of Modifiers: Product Modifiers
• A combinatorial approach for the state complexity of the shuffle product
• A general approach to state complexity of operations: formalization and limitations
• A survey on operational state complexity
• AUTOMATE, a computing package for automata and finite semigroups
• Combination of roots and Boolean operations: an application to state complexity
• Estimation of state complexity of combined operations
• In search of most complex regular languages
• Intersection and union of regular languages and state complexity
• New tools for state complexity
• Nondeterminism and the size of two way finite automata
• On the state complexity of reversals of regular languages
• On the state complexity of star of union and star of intersection
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• State complexity of basic language operations combined with reversal
• State complexity of catenation combined with a Boolean operation: a unified approach
• State complexity of combined operations
• State complexity of combined operations involving catenation and binary Boolean operations: beyond the Brzozowski conjectures
• State complexity of multiple catenations
• State complexity of some operations on binary regular languages
• State complexity of two combined operations: catenation-union and catenation-intersection
• The exact complexity of star-complement-star
• The state complexities of some basic operations on regular languages
• The state complexity of star-complement-star
• The state complexity of two combined operations: star of catenation and star of reversal

This page was built for publication: Operational state complexity revisited: the contribution of monsters and modifiers

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