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;]

---

Logical properties of random graphs from small addable classes

Anuj Dawar ; Eryk Kopczyński.

We establish zero-one laws and convergence laws for monadic second-order logic (MSO) (and, a fortiori, first-order logic) on a number of interesting graph classes. In particular, we show that MSO obeys a zero-one law on the class of connected planar graphs, the class of connected graphs of&nbsp;[&hellip;]

---