Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat 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.
2017 (Engelska)Ingår i: Fundamenta Informaticae, ISSN 0169-2968, E-ISSN 1875-8681, Vol. 155, s. 89-110Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We investigate the state complexity of the cut and iterated cut operation for determin- istic 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 al- ternative 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 states, if m = 1, and (n−1)·m+n states, otherwise, on DFAs accepting the cut of two individual languages that are ac- cepted by n- and m-state DFAs, respectively. In the unary case we obtain max(2n − 1, m + n − 2) states as a tight bound—notice that for m ≤ n the bound for unary DFAs only depends on the former automaton and not on the latter. 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) states on DFAs, if n ≥ 4 and where F refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n − 1)!). Finally, the bound drops to 2n − 1 for unary DFAs accepting the iterated cut of an n-state DFA, if n ≥ 3, and thus is similar to the bound for the cut operation on unary DFAs.

Ort, förlag, år, upplaga, sidor
IOS Press, 2017. Vol. 155, s. 89-110
Nyckelord [en]
finite automata, cut and iterated cut operation, descriptional complexity
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-136263DOI: 10.3233/FI-2017-1577ISI: 000411029200005Scopus ID: 2-s2.0-85029478388ISBN: 978-3-319-23111-2 (tryckt)ISBN: 978-3-319-23110-5 (tryckt)OAI: oai:DiVA.org:umu-136263DiVA, id: diva2:1110075
Tillgänglig från: 2017-06-15 Skapad: 2017-06-15 Senast uppdaterad: 2023-03-24Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Drewes, Frank

Sök vidare i DiVA

Av författaren/redaktören
Drewes, Frank
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
Fundamenta Informaticae
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 721 träffar
RefereraExporteraLänk till posten
Permanent länk

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