umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Tight Bounds for Cut-Operations on Deterministic Finite Automata
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Natural and Formal Languages)ORCID-id: 0000-0001-7349-7693
Universität Giessen.
Universität Giessen.
University of Stellenbosch.
2015 (engelsk)Inngår i: Machines, Computations, and Universality: 7th International Conference, MCU 2015, Famagusta, North Cyprus, September 9-11, 2015, Proceedings / [ed] J. Durand-Lose and B. Nagy, Springer Publishing Company, 2015, Vol. 9288, s. 45-60Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

We investigate the state complexity of the cut and iterated cut operation for deterministic finite automata (DFAs), answering an open question stated in [M. Berglund, et al.: Cuts in regular expressions. In Proc. DLT, LNCS 7907, 2011]. These operations can be seen as an alternative to ordinary concatenation and Kleene star modelling leftmost maximal string matching. We show that the cut operation has a matching upper and lower bound of (n−1)⋅m+n(n−1)⋅m+n states on DFAs accepting the cut of two individual languages that are accepted by n- and m-state DFAs, respectively. In the unary case we obtain max(2n−1,m+n−2)max(2n−1,m+n−2) states as a tight bound. For accepting the iterated cut of a language accepted by an n-state DFA we find a matching bound of 1+(n+1)⋅F(1,n+2,−n+2;n+1∣−1)1+(n+1)⋅F(1,n+2,−n+2;n+1∣−1) states on DFAs, where FF refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n−1)!)Θ((n−1)!). Finally, the bound drops to 2n−12n−1 for unary DFAs accepting the iterated cut of an n-state DFA and thus is similar to the bound for the cut operation on unary DFAs.

sted, utgiver, år, opplag, sider
Springer Publishing Company, 2015. Vol. 9288, s. 45-60
Serie
Lecture Notes in Computer Science, ISSN 0302-9743
HSV kategori
Forskningsprogram
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-104114DOI: 10.1007/978-3-319-23111-2_4ISI: 000363670900004ISBN: 978-3-319-23111-2 (tryckt)ISBN: 978-3-319-23110-5 (tryckt)OAI: oai:DiVA.org:umu-104114DiVA, id: diva2:817777
Konferanse
7th Conference on Machines, Computations and Universality (MCU 2015)
Tilgjengelig fra: 2015-06-06 Laget: 2015-06-06 Sist oppdatert: 2018-06-07bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Drewes, Frank

Søk i DiVA

Av forfatter/redaktør
Drewes, Frank
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 543 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf