9
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Syntactic Complexity of Circular Semi-Flower Automata

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We investigate the syntactic complexity of certain types of finitely generated submonoids of a free monoid. In fact, we consider those submonoids which are accepted by circular semi-flower automata (CSFA). Here, we show that the syntactic complexity of CSFA with at most one `branch point going in' (bpi) is linear. Further, we prove that the syntactic complexity of \(n\)-state CSFA with two bpis over a binary alphabet is \(2n(n+1)\).

          Related collections

          Author and article information

          Journal
          2013-06-14
          Article
          1306.3492
          60252d42-76f9-4259-9c0a-400a17c66e68

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          68Q70, 68Q45, 20M35
          cs.FL

          Theoretical computer science
          Theoretical computer science

          Comments

          Comment on this article