GF(2)-operations on basic families of formal languages

DOI10.1016/J.TCS.2024.114489MaRDI QIDQ6204546zbMATH OpenFDO

Authors Alexander Okhotin, Maria Radionova, Elizaveta Sazhneva

Publication date 28 March 2024

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

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114489

zbMATH Keywords

\(\mathrm{GF}(2)\)-concatenation\(\mathrm{GF}(2)\)-inverse\(\mathrm{GF}(2)\)-starcellular automatadeterministic pushdown automatafinite automatagroup languagespermutation automatatrellis automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Formal languages over GF(2)
• Formal languages over GF(2)
• State complexity of GF(2)-operations on unary languages
• On the expressive power of GF(2)-grammars
• State complexity of GF(2)-concatenation and GF(2)-inverse on unary languages

Cites work

• A property of real-time trellis automata
• A tale of conjunctive grammars
• Algebraic systems and pushdown automata
• Bounded languages described by GF(2)-grammars
• Characterizations and computational complexity of systolic trellis automata
• Closure properties of cellular automata
• Deterministic context free languages
• Formal languages over GF(2)
• Handbook of weighted automata
• scientific article; zbMATH DE number 3972214 (Why is no real title available?)
• Language not recognizable in real time by one-way cellular automata
• Non-closure under complementation for unambiguous linear grammars
• On real time one-way cellular array
• On the equivalence of linear conjunctive grammars and trellis automata
• On the expressive power of GF(2)-grammars
• On time computability of functions in one-way cellular automata
• One-way bounded cellular automata
• Operations on Permutation Automata
• Permutation automata
• Preservation of unambiguity and inherent ambiguity in context-free languages
• Real-time language recognition by one-dimensional cellular automata
• Semirings and Formal Power Series
• Some computational limits of trellis automata
• State complexity of GF(2)-operations on unary languages
• Systolic trellis automatata †
• Systolic trellis automatat†
• The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages

Cited in

(4)

• Formal languages over GF(2)
• Sweeping permutation automata
• A hierarchy of reversible finite automata
• Reversible weighted automata over finite rings and monoids with commuting idempotents

This page was built for publication: \(\mathrm{GF}(2)\)-operations on basic families of formal languages

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