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

DOI10.1016/J.IC.2021.104693OpenAlexW3120719177MaRDI QIDQ2113387FDOQ2113387

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)

Cites Work

• The state complexities of some basic operations on regular languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal simulations between unary automata
• Unambiguous finite automata over a unary alphabet
• Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
• Converting two-way nondeterministic unary automata into simpler automata.
• Quotient complexity of regular languages
• On the expressive power of GF(2)-grammars
• Formal languages over GF(2)
• State complexity of unambiguous operations on finite automata
• State complexity of GF(2)-concatenation and GF(2)-inverse on unary languages
• Ambiguity of Unary Symmetric Difference NFAs
• Minimal DFA for Symmetric Difference NFA
• Title not available (Why is that?)
• Formal languages over GF(2)

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(\mathrm{GF}(2)\)-operations on basic families of formal languages

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)