Flowchart Programs, Regular Expressions, and Decidability of Polynomial Growth-Rate

Article, Preprint English OPEN
Ben-Amram, Amir M.; Pineles, Aviad;
(2016)
  • Publisher: Open Publishing Association
  • Journal: Electronic Proceedings in Theoretical Computer Science (issn: 2075-2180)
  • Publisher copyright policies & self-archiving
  • Related identifiers: doi: 10.4204/EPTCS.216.2
  • Subject: Computer Science - Programming Languages | Mathematics | Electronic computers. Computer science | Computer Science - Formal Languages and Automata Theory | Computer Science - Logic in Computer Science | QA1-939 | QA75.5-76.95
    acm: TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
    arxiv: Computer Science::Programming Languages

We present a new method for inferring complexity properties for a class of programs in the form of flowcharts annotated with loop information. Specifically, our method can (soundly and completely) decide if computed values are polynomially bounded as a function of the i... View more
  • References (1)

    Aviad Pineles. Growth-rate analysis of flowchart programs. MSc project, The Academic College of Tel-Aviv Yaffo, 2014.

  • Metrics
Share - Bookmark