State complexity of inversion operations

DOI10.1016/j.tcs.2015.04.017zbMath1332.68110OpenAlexW2174018860MaRDI QIDQ896671

Da-Jung Cho, Sang-Ki Ko, Yo-Sub Han, Kai Salomaa

Publication date: 10 December 2015

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

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

zbMATH Keywords

finite automataregular languagesstate complexityinversion operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Efficient string-matching allowing for non-overlapping inversions
• Reversal of binary regular languages
• Descriptional and computational complexity of finite automata -- a survey
• Succinct representation of regular languages by Boolean automata
• Intersection and union of regular languages and state complexity
• The state complexities of some basic operations on regular languages
• Closure and decidability properties of some language classes with respect to ciliate bio-operations.
• Estimation of state complexity of combined operations
• State complexity of combined operations
• On Decidability and Closure Properties of Language Classes with Respect to Bio-operations
• Pseudo-inversion on Formal Languages
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Operations and language generating devices suggested by the genome evolution
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: State complexity of inversion operations