The State Complexity of Permutations on Finite Languages over Binary Alphabets

DOI10.1007/978-3-319-19225-3_19zbMath1432.68241OpenAlexW843209405MaRDI QIDQ5500695

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

Publication date: 7 August 2015

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-19225-3_19

zbMATH Keywords

permutationfinite automatastate complexityfinite languagesParikh equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Unnamed Item ⋮ State complexity of permutation and related decision problems on alphabetical pattern constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• The state complexities of some basic operations on regular languages
• Nondeterministic State Complexity of Proportional Removals
• STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES
• A Second Course in Formal Languages and Automata Theory
• Operational State Complexity under Parikh Equivalence
• On Context-Free Languages
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• A logical calculus of the ideas immanent in nervous activity

This page was built for publication: The State Complexity of Permutations on Finite Languages over Binary Alphabets