State complexity of permutation on finite languages over a binary alphabet

DOI10.1016/j.tcs.2017.03.007zbMath1371.68145OpenAlexW2595036685MaRDI QIDQ2358683

Yo-Sub Han, Kai Salomaa, Daniel Goč, Sang-Ki Ko, Da-Jung Cho, Alexandros Palioudakis

Publication date: 15 June 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.03.007

zbMATH Keywords

finite automatastate complexityfinite languagesParikh equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs, Unnamed Item, On Simon's congruence closure of a string, Unnamed Item, The Ranges of Accepting State Complexities of Languages Resulting from Some Operations, On Simon's congruence closure of a string, State complexity of permutation and related decision problems on alphabetical pattern constraints

Cites Work

• Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
• State complexity of combined operations with two basic operations
• Descriptional and computational complexity of finite automata -- a survey
• On deterministic finite automata and syntactic monoid size
• Operational state complexity of unary NFAs with finite nondeterminism
• Lower bounds for the transition complexity of NFAs
• The state complexities of some basic operations on regular languages
• On the average state and transition complexity of finite languages
• From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity
• On the State Complexity of the Shuffle of Regular Languages
• Undecidability of state complexity
• State Complexity of Basic Operations on Non-Returning Regular Languages
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• A Second Course in Formal Languages and Automata Theory
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
• Descriptional Complexity of Union and Star on Context-Free Languages
• Descriptional Complexity of Chop Operations on Unary and Finite Languages.
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
• Operational State Complexity under Parikh Equivalence
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item