Combination of roots and Boolean operations: an application to state complexity

DOI10.1016/J.IC.2022.104961MaRDI QIDQ2105451zbMATH OpenOpenAlexFDO

Authors Pascal Caron, Edwin Hamel-de le Court, Jean-Gabriel Luque

Publication date 8 December 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2022.104961

zbMATH Keywords

finite automataformal languagesstate complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• State complexity of catenation combined with a Boolean operation: a unified approach
• State complexity of combined operations involving catenation and binary Boolean operations: beyond the Brzozowski conjectures
• The exact state complexity for the composition of root and reversal
• The complexity of Boolean state separation
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• State complexity of combined operations with two basic operations
• State complexity of combined operations
• The complexity of Boolean matrix root computation
• The complexity of Boolean matrix root computation

Cites work

• A general approach to state complexity of operations: formalization and limitations
• A survey on operational state complexity
• Algebraic and combinatorial tools for state complexity: application to the star-xor problem
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 2068872 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• In search of most complex regular languages
• New tools for state complexity
• On the State Complexity of the Shuffle of Regular Languages
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• State complexity of cyclic shift
• State complexity of regular languages
• State complexity of some operations on binary regular languages

Cited in

(4)

• Primitivity, uniform minimality, and state complexity of Boolean operations
• A Study of a Simple Class of Modifiers: Product Modifiers
• The exact state complexity for the composition of root and reversal
• Operational state complexity revisited: the contribution of monsters and modifiers

This page was built for publication: Combination of roots and Boolean operations: an application to state complexity

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