SwePub
Sök i LIBRIS databas

  Extended search

id:"swepub:oai:DiVA.org:umu-88231"
 

Search: id:"swepub:oai:DiVA.org:umu-88231" > Characterizing Non-...

  • 1 of 1
  • Previous record
  • Next record
  •    To hitlist

Characterizing Non-Regularity

Berglund, Martin, 1981- (author)
Umeå universitet,Institutionen för datavetenskap,Naturliga och Formella Språk
Björklund, Henrik, 1973- (contributor)
Umeå universitet,Institutionen för datavetenskap,Naturliga och Formella Språk
Drewes, Frank, 1963- (contributor)
Umeå universitet,Institutionen för datavetenskap,Naturliga och Formella Språk
 (creator_code:org_t)
Umeå : Umeå universitet, 2014
English 9 s.
Series: Report / UMINF, 0348-0542 ; 14.12
  • Reports (other academic/artistic)
Abstract Subject headings
Close  
  • This paper considers a characterization of the context-free non-regular languages, conjecturing that there for all such languages exists a fixed string thatcan be pumped to exhibit infinitely many equivalence classes. A proof is given only for a special case, but the general statement is conjectured to hold. The conjecture is then shown to imply that the shuffle of two context-free languagesis not context-free.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Keyword

context-free languages
characterization
regular languages
pumping lemma
shuffle
Computer Science
datalogi

Publication and Content Type

vet (subject category)
rap (subject category)

To the university's database

  • 1 of 1
  • Previous record
  • Next record
  •    To hitlist

Find more in SwePub

By the author/editor
Berglund, Martin ...
Björklund, Henri ...
Drewes, Frank, 1 ...
About the subject
NATURAL SCIENCES
NATURAL SCIENCES
and Computer and Inf ...
and Computer Science ...
Parts in the series
Report / UMINF,
By the university
Umeå University

Search outside SwePub

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Close

Copy and save the link in order to return to this view