State complexity of GF(2)-operations on unary languages

DOI10.1016/J.IC.2021.104693MaRDI QIDQ2113387zbMATH OpenOpenAlexFDO

Authors Alexander Okhotin, Elizaveta Sazhneva

Publication date 14 March 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2021.104693

zbMATH Keywords

primitive polynomialsstate complexityGF(2)-concatenationGF(2)-inverseGF(2)-star

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• State complexity of GF(2)-concatenation and GF(2)-inverse on unary languages
• State complexity of some operations on binary regular languages
• Formal languages over GF(2)
• scientific article; zbMATH DE number 1773089
• The state complexities of some basic operations on regular languages

Cites work

• scientific article; zbMATH DE number 4083539 (Why is no real title available?)
• scientific article; zbMATH DE number 7444008 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• Ambiguity of unary symmetric difference NFAs
• Converting two-way nondeterministic unary automata into simpler automata.
• Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
• Formal languages over GF(2)
• Formal languages over GF(2)
• Minimal DFA for symmetric difference NFA
• On the expressive power of GF(2)-grammars
• Optimal simulations between unary automata
• Orthogonal concatenation: language equations and state complexity
• Quotient complexity of regular languages
• State complexity of GF(2)-concatenation and GF(2)-inverse on unary languages
• State complexity of unambiguous operations on finite automata
• The state complexities of some basic operations on regular languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Unambiguous finite automata over a unary alphabet

Cited in

(4)

• scientific article; zbMATH DE number 7770054 (Why is no real title available?)
• scientific article; zbMATH DE number 6855103 (Why is no real title available?)
• \(\mathrm{GF}(2)\)-operations on basic families of formal languages
• scientific article; zbMATH DE number 1948495 (Why is no real title available?)

This page was built for publication: State complexity of GF(2)-operations on unary languages

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