State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
type: Item
instance of: scholarly article
title: State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
author: Stefan Hoffmann
published in: Information and Computation
publication date: 2024-12-03T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7953353
zbMATH Keywords: commutative regular language
zbMATH Keywords: state complexity
zbMATH Keywords: finite automata
zbMATH Keywords: index and period vector
zbMATH Keywords: shuffle
zbMATH Keywords: upward closure
MaRDI profile type: Publication
cites work: Commutative Positive Varieties of Languages
cites work: QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
cites work: Characterizations of locally testable events
cites work: On the State Complexity of the Shuffle of Regular Languages
cites work: Q4807824
cites work: State complexity of permutation on finite languages over a binary alphabet
cites work: On regularity of context-free languages
cites work: Q3948597
cites work: Q3948598
cites work: Modeling literal morphisms by shuffle
cites work: Q5208373
cites work: Q4590910
cites work: Bounded Regular Sets
cites work: Learning Commutative Regular Languages
cites work: Regular languages and partial commutations
cites work: The size of Higman-Haines sets
cites work: More on the Size of Higman-Haines Sets: Effective Constructions
cites work: On free monoids partially ordered by embedding
cites work: On Shuffle Ideals
cites work: Ordering by Divisibility in Abstract Algebras
cites work: Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
cites work: State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
cites work: Commutative regular languages -- properties and state complexity
cites work: Commutative regular languages with product-form minimal automata
cites work: Descriptional complexity of formal systems. 23rd IFIP WG 1.02 international conference, DCFS 2021, virtual event, September 5, 2021. Proceedings
cites work: State complexity of projection on languages recognized by permutation automata and commuting letters
cites work: Q3862379
cites work: Q3929056
cites work: Q4217599
cites work: Algebraic Theory of Automata and Languages
cites work: The power of synchronizing operations on strings
cites work: On a structural property in the state complexity of projected regular languages
cites work: On the state complexity of closures and interiors of regular languages with subwords and superwords
cites work: Commutative one-counter languages are regular
cites work: Q5628039
cites work: The loop complexity of pure-group events
cites work: Q5641083
cites work: JUMPING FINITE AUTOMATA
cites work: Linear Automaton Transformations
cites work: On the State Complexity of Scattered Substrings and Superstrings
cites work: On Context-Free Languages
cites work: Variétés de langages et opérations
cites work: UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
cites work: Q3769981
cites work: Q4714446
cites work: Q4991691
cites work: On the Burnside problem for semigroups
cites work: Q4884899
cites work: On finite monoids having only trivial subgroups
cites work: Permutation automata
cites work: Effective constructions in well-partially-ordered free monoids
cites work: The state complexities of some basic operations on regular languages
cites work: Operational State Complexity under Parikh Equivalence
cites work: An Approach to Computing Downward Closures
cites work: Q6070603
cites work: Reset words for commutative and solvable automata
cites work: Classifying Regular Languages via Cascade Products of Automata
cites work: The expressive power of the shuffle product
DOI: 10.1016/J.IC.2024.105204
description: scientific article; zbMATH DE number 7953353