State complexity of inversion operations

DOI10.1016/J.TCS.2015.04.017MaRDI QIDQ896671zbMATH OpenOpenAlexFDO

Authors Da-Jung Cho, Yo-Sub Han, Sang-Ki Ko, 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 automatainversion operationsregular languagesstate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of inversion operations
• On the state complexity of reversals of regular languages
• State complexity of basic language operations combined with reversal
• Prefix-free languages: right quotient and reversal
• Reversal of binary regular languages

Cites work

• Closure and decidability properties of some language classes with respect to ciliate bio-operations.
• Descriptional and computational complexity of finite automata -- a survey
• Efficient string-matching allowing for non-overlapping inversions
• Estimation of state complexity of combined operations
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• Intersection and union of regular languages and state complexity
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On decidability and closure properties of language classes with respect to bio-operations
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• Operations and language generating devices suggested by the genome evolution
• Pseudo-inversion on formal languages
• Recent trends in descriptional complexity of formal languages
• Reversal of binary regular languages
• State complexity of combined operations
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages
• The state complexity of two combined operations: star of catenation and star of reversal

Cited in

(5)

• Pseudo-inversion on formal languages
• State complexity of cyclic shift
• Non-overlapping inversion on strings and languages
• scientific article; zbMATH DE number 6415494 (Why is no real title available?)
• State complexity of inversion operations

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

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