2016

  1. Majority Digraphs
    Tri Lai, Jörg Endrullis, and Lawrence S. Moss
    Proceedings of the American Mathematical Society , 144 (9) , pp. 3701–3715 (2016)
    paper

    Summary

    A majority digraph is a finite simple digraph \( G = (V,\to) \) such that there exist finite sets \( A_v \) for the vertices \( v \in V \) with the following property: \( u \to v \) if and only if "more than half of the \( A_u \) are \( A_v \)". That is, \( u \to v \) if and only if \( | A_u \cap A_v | > \frac{1}{2} \cdot | A_u | \) . We characterize the majority digraphs as the digraphs with the property that every directed cycle has a reversal. If we change to any real number \( \alpha \in (0, 1) \), we obtain the same class of digraphs. We apply the characterization result to obtain a result on the logic of assertions "most X are Y" and the standard connectives of propositional logic.

    Bibtex

    @article{logic:most:graphs:2016,
  author = {Lai, Tri and Endrullis, J{\"o}rg and Moss, {Lawrence S.}},
  title = {Majority digraphs},
  journal = {Proceedings of the American Mathematical Society},
  publisher = {American Mathematical Society},
  volume = {144},
  number = {9},
  pages = {3701--3715},
  year = {2016},
  doi = {10.1090/proc/13038},
  keywords = {logic},
  type = {journal}
}

    Digital Object Identifier

    10.1090/proc/13038
  2. Degrees of Infinite Words, Polynomials and Atoms
    Jörg Endrullis, Juhani Karhumäki, Jan Willem Klop, and Aleksi Saarela
    In: Proc. Conf. on Developments in Language Theory (DLT 2016), pp. 164–176, Springer (2016)
    paper

    Summary

    A finite state transducer is a finite automaton that transforms input words into output words. The transducer reads the input letter by letter, in each step producing an output word and changing its state.

    While finite state transducers are very simple and elegant devices, their power in transforming infinite words is hardly understood.

    In this paper we show that techniques from continuous mathematics can be used to reason about finite state transducers. To be precise, we use the following methods from linear algebra and analysis:

    • continuity,
    • Vandermonde matrices,
    • invertibility of matrices, and
    • the generalised mean inequality.
    We employ these techniques to obtain both positive and negative results on transducibility.

    The main result in this paper is the existance of an infinite number of atoms in the hierarchy of streams arising from finite state transduction.

    We have published an extended journal version of this paper in the International Journal of Foundations of Computer Science, 2018.

    See research for an introduction to finite state transducers, an overview of my research and many open questions.

    Bibtex

    @inproceedings{streams:degrees:polynomials:2016,
  author = {Endrullis, J\"{o}rg and Karhum{\"{a}}ki, Juhani and Klop, Jan Willem and Saarela, Aleksi},
  title = {{Degrees of Infinite Words, Polynomials and Atoms}},
  booktitle = {Proc.\ Conf.\ on Developments in Language Theory (DLT~2016)},
  volume = {9840},
  pages = {164--176},
  publisher = {Springer},
  series = {LNCS},
  year = {2016},
  doi = {10.1007/978-3-662-53132-7\_14},
  keywords = {streams, degrees, automata},
  type = {conference}
}

    Digital Object Identifier

    10.1007/978-3-662-53132-7_14