Primitivity, uniform minimality, and state complexity of Boolean operations

DOI10.1007/s00224-018-9859-0zbMath1430.68142arXiv1702.00877OpenAlexW2592641503MaRDI QIDQ2322701

Sylvie Davies

Publication date: 5 September 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1702.00877

zbMATH Keywords

finite automatonstate complexityprimitive groupBoolean operationuniformly minimaltransition monoid

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Binary and circular automata having maximal state complexity for the set of synchronizing words ⋮ New characterizations of primitive permutation groups with applications to synchronizing automata

Uses Software

• GAP
• Magma
• automata

Cites Work

• A graph theoretic approach to automata minimality
• Extremal minimality conditions on automata
• On the state complexity of reversals of regular languages
• A theory of transformation monoids: combinatorics and representation theory
• The state complexities of some basic operations on regular languages
• The Magma algebra system. I: The user language
• Quotient complexity of ideal languages
• Estimation of state complexity of combined operations
• State complexity of combined operations
• Between primitive and 2-transitive: synchronization and its friends
• Unrestricted State Complexity of Binary Operations on Regular Languages
• Finite Permutation Groups and Finite Simple Groups
• STATE COMPLEXITY AND APPROXIMATION
• QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
• Symmetric Groups and Quotient Complexity of Boolean Operations
• IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
• Semisimple Synchronizing Automata and the Wedderburn-Artin Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Primitivity, uniform minimality, and state complexity of Boolean operations