State complexity of projection on languages recognized by permutation automata and commuting letters

DOI10.1007/978-3-030-81508-0_16MaRDI QIDQ832938zbMATH OpenOpenAlexFDO

Authors Stefan Hoffmann

Publication date 25 March 2022

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

zbMATH Keywords

projectionfinite automatastate complexitycommutative automatapermutation automatastate-partition automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of projected languages
• On properties and state complexity of deterministic state-partition automata
• On a structural property in the state complexity of projected regular languages
• Operations on Permutation Automata
• On the accepting state complexity of operations on permutation automata

Cites work

• scientific article; zbMATH DE number 3647158 (Why is no real title available?)
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• scientific article; zbMATH DE number 706263 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• A survey on operational state complexity
• Complexity of proper prefix-convex regular languages
• Coordination control of distributed discrete-event systems
• Finite-state techniques. Automata, transducers and bimachines
• Introduction to Discrete Event Systems
• Languages recognized by finite supersoluble groups
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• On a structural property in the state complexity of projected regular languages
• On properties and state complexity of deterministic state-partition automata
• Operations on Permutation Automata
• Permutation automata
• Supervisory control of discrete-event systems
• Supervisory control synthesis of discrete-event systems using a coordination scheme
• The loop complexity of pure-group events
• The mathematical writings of Évariste Galois
• The state complexities of some basic operations on regular languages

Cited in

(7)

• State complexity of permutation and related decision problems on alphabetical pattern constraints
• Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
• Nondeterministic operational complexity in subregular languages
• State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
• VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states
• Commutative regular languages with product-form minimal automata
• State complexity investigations on commutative languages -- the upward and downward closure, commutative aperiodic and commutative group languages

Describes a project that uses

Uses Software

• UMDES

This page was built for publication: State complexity of projection on languages recognized by permutation automata and commuting letters

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