Search

• < Previous
• 1
• Next >

---

Complexity of Problems of Commutative Grammars

Eryk Kopczynski.

We consider commutative regular and context-free grammars, or, in other words, Parikh images of regular and context-free languages. By using linear algebra and a branching analog of the classic Euler theorem, we show that, under an assumption that the terminal alphabet is fixed, the membership&nbsp;[&hellip;]

---

Definability of linear equation systems over groups and rings

Anuj Dawar ; Eryk Kopczynski ; Bjarki Holm ; Erich Grädel ; Wied Pakusa.

Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the solvability of linear equation systems over finite groups and rings from the viewpoint of logical (inter-)definability.&nbsp;[&hellip;]

---