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