Complexity of regular functions

Eric Allender, Ian Mertz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

We give complexity bounds for various classes of functions computed by cost register automata.

Original languageEnglish (US)
Title of host publicationLanguage and Automata Theory and Applications - 9th International Conference, LATA 2015, Proceedings
EditorsAdrian-Horia Dediu, Carlos Martín-Vide, Enrico Formenti, Bianca Truthe
PublisherSpringer Verlag
Pages449-460
Number of pages12
ISBN (Electronic)9783319155784
DOIs
StatePublished - 2015
Event9th International Conference on Language and Automata Theory and Applications, LATA 2015 - Nice, France
Duration: Mar 2 2015Mar 6 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8977
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Conference on Language and Automata Theory and Applications, LATA 2015
Country/TerritoryFrance
CityNice
Period3/2/153/6/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Computational complexity
  • Transducers
  • Weighted automata

Fingerprint

Dive into the research topics of 'Complexity of regular functions'. Together they form a unique fingerprint.

Cite this