Algebraic and combinatorial tools for state complexity: application to the star-xor problem

MaRDI QIDQ5020533zbMATH OpenFDO

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

Publication date 6 January 2022

Full work available at URL https://arxiv.org/abs/1909.07663, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF2019.11

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Applications of game theory (91A80) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• New tools for state complexity
• On the state complexity of star of union and star of intersection
• The exact complexity of star-complement-star
• On the State Complexity of Combined Operations
• The state complexity of star-complement-star

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?)
• A general approach to state complexity of operations: formalization and limitations
• A survey on operational state complexity
• In search of most complex regular languages
• On the State Complexity of the Shuffle of Regular Languages
• On the state complexity of star of union and star of intersection
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• 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 cyclic shift
• State complexity of power
• State complexity of regular languages
• State complexity of some operations on binary regular languages
• State complexity of two combined operations: catenation-union and catenation-intersection
• The state complexity of two combined operations: star of catenation and star of reversal

Cited in

(4)

• Combination of roots and Boolean operations: an application to state complexity
• State complexity of permutation and related decision problems on alphabetical pattern constraints
• Operational state complexity revisited: the contribution of monsters and modifiers
• A Study of a Simple Class of Modifiers: Product Modifiers

This page was built for publication: Algebraic and combinatorial tools for state complexity: application to the star-xor problem

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