Formal languages over GF(2)
From MaRDI portal
Publication:5918612
DOI10.1016/j.ic.2020.104672OpenAlexW3113377019MaRDI QIDQ5918612
Igor Batmanov, Alexander Okhotin, Ekaterina Bakinova, Artem Basharin, Konstantin Lyubort, 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.2020.104672
computational complexityfinite fieldsfinite automataformal languagesstate complexityparsingformal grammars
Related Items (4)
\(\mathrm{GF}(2)\)-operations on basic families of formal languages ⋮ Unnamed Item ⋮ Special issue: Selected papers of the 12th international conference on language and automata theory and applications, LATA 2018 ⋮ State complexity of GF(2)-operations on unary languages
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parsing by matrix multiplication generalized to Boolean grammars
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- On the expressive power of univariate equations over sets of natural numbers
- Unambiguous conjunctive grammars over a one-symbol alphabet
- Complexity of equations over sets of natural numbers
- On binary circle plus operator \(\oplus\)-NFAs and succinct descriptions of regular languages
- Problems complete for \(\oplus L\)
- Observations on \(\log(n)\) time parallel recognition of unambiguous cfl's
- General context-free recognition in less than cubic time
- Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets)
- The state complexities of some basic operations on regular languages
- Unrestricted complementation in language equations over a one-letter alphabet
- \(L(A)=L(B)\)? decidability results from complete formal systems
- Underlying principles and recurring ideas of formal grammars
- State complexity of GF(2)-concatenation and GF(2)-inverse on unary languages
- On the expressive power of GF(2)-grammars
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- State complexity of unambiguous operations on finite automata
- Algorithm 898
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- On the equivalence of linear conjunctive grammars and trellis automata
- Algebraic Systems and Pushdown Automata
- Two Families of Languages Related to ALGOL
This page was built for publication: Formal languages over GF(2)
