\(\mathrm{GF}(2)\)-operations on basic families of formal languages
From MaRDI portal
Publication:6204546
DOI10.1016/j.tcs.2024.114489MaRDI QIDQ6204546
Elizaveta Sazhneva, Maria Radionova, Alexander Okhotin
Publication date: 28 March 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
cellular automatafinite automatadeterministic pushdown automatagroup languagespermutation automatatrellis automata\(\mathrm{GF}(2)\)-concatenation\(\mathrm{GF}(2)\)-inverse\(\mathrm{GF}(2)\)-star
Cites Work
- Unnamed Item
- On real time one-way cellular array
- Characterizations and computational complexity of systolic trellis automata
- Closure properties of cellular automata
- Bounded languages described by GF(2)-grammars
- Handbook of weighted automata
- A property of real-time trellis automata
- On time computability of functions in one-way cellular automata
- Language not recognizable in real time by one-way cellular automata
- A tale of conjunctive grammars
- Some computational limits of trellis automata
- State complexity of GF(2)-operations on unary languages
- On the expressive power of GF(2)-grammars
- Real-time language recognition by one-dimensional cellular automata
- Systolic trellis automatata †
- Systolic trellis automatat†
- One-way bounded cellular automata
- On the equivalence of linear conjunctive grammars and trellis automata
- Operations on Permutation Automata
- Semirings and Formal Power Series
- Algebraic Systems and Pushdown Automata
- Preservation of unambiguity and inherent ambiguity in context-free languages
- Deterministic context free languages
- The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages
- Permutation automata
- Formal languages over GF(2)
- Non-closure under complementation for unambiguous linear grammars
This page was built for publication: \(\mathrm{GF}(2)\)-operations on basic families of formal languages
