Operations on Permutation Automata

DOI10.1007/978-3-030-48516-0_10OpenAlexW3028843709MaRDI QIDQ5041254

Peter Mlynárčik, Michal Hospodár

Publication date: 13 October 2022

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-48516-0_10

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (8)

State complexity of projection on languages recognized by permutation automata and commuting letters ⋮ Nondeterministic operational complexity in subregular languages ⋮ On the accepting state complexity of operations on permutation automata ⋮ \(\mathrm{GF}(2)\)-operations on basic families of formal languages ⋮ Unnamed Item ⋮ Unnamed Item ⋮ State complexity investigations on commutative languages -- the upward and downward closure, commutative aperiodic and commutative group languages ⋮ Closure properties of subregular languages under operations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The state complexity of \(L^{2}\) and \(L^k\)
• State complexity of basic operations on suffix-free regular languages
• The state complexities of some basic operations on regular languages
• Quotient complexity of closed languages
• Quotient complexity of ideal languages
• NFA-to-DFA trade-off for regular operations
• The range of state complexities of languages resulting from the cut operation
• COMPLEXITY IN UNION-FREE REGULAR LANGUAGES
• Kleene closure and state complexity
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• State complexity of cyclic shift
• Complexity of Operations on Cofinite Languages
• Tight Bounds for Cut-Operations on Deterministic Finite Automata*
• QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
• Cuts in Regular Expressions
• Permutation automata

This page was built for publication: Operations on Permutation Automata