Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
2 results

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;]
Published on March 25, 2015
Volume 11, Issue 1

A note on first-order spectra with binary relations

Eryk Kopczynski ; Tony Tan.
The spectrum of a first-order sentence is the set of the cardinalities of its finite models. In this paper, we consider the spectra of sentences over binary relations that use at least three variables. We show that for every such sentence $\Phi$, there is a sentence $\Phi'$ that uses the same number&nbsp;[&hellip;]
Published on April 25, 2018
Volume 14, Issue 2
  • < Previous
  • 1
  • Next >