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

DOI10.1016/j.ic.2022.104961OpenAlexW4295941584MaRDI QIDQ2105451

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

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)

Related Items

The exact state complexity for the composition of root and reversal ⋮ Operational state complexity revisited: the contribution of monsters and modifiers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A general approach to state complexity of operations: formalization and limitations
• State complexity of some operations on binary regular languages
• On the State Complexity of the Shuffle of Regular Languages
• State complexity of cyclic shift
• IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET