Graphs capturing alternations in words

Magnus Halldorsson, Sergey Kitaev, Artem Pyatkin

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

13 Citations (Scopus)

Abstract

A graph G = (V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x, y) ∈ E for each x ≠ y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. A graph is representable if and only if it is k-representable for some k [1].
LanguageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings
EditorsYuan Gao, Hanlin Lu, Shinnosuke Seki, Sheng Yu
Pages436-437
Number of pages2
DOIs
Publication statusPublished - 2010
Event14th Conference on Dvelopments in Language Theory - London, Ontario, Canada
Duration: 17 Aug 201020 Aug 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume6224
ISSN (Print)0302-9743

Conference

Conference14th Conference on Dvelopments in Language Theory
CountryCanada
CityLondon, Ontario
Period17/08/1020/08/10

Fingerprint

Alternation
If and only if
Graph in graph theory
Alternate

Keywords

  • algorithm analysis
  • graphs
  • word patterns

Cite this

Halldorsson, M., Kitaev, S., & Pyatkin, A. (2010). Graphs capturing alternations in words. In Y. Gao, H. Lu, S. Seki, & S. Yu (Eds.), Developments in Language Theory: 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings (pp. 436-437). (Lecture Notes in Computer Science; Vol. 6224). https://doi.org/10.1007/978-3-642-14455-4_41
Halldorsson, Magnus ; Kitaev, Sergey ; Pyatkin, Artem. / Graphs capturing alternations in words. Developments in Language Theory: 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings. editor / Yuan Gao ; Hanlin Lu ; Shinnosuke Seki ; Sheng Yu. 2010. pp. 436-437 (Lecture Notes in Computer Science).
@inproceedings{b16608e181314f368e0801b01c48cbf7,
title = "Graphs capturing alternations in words",
abstract = "A graph G = (V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x, y) ∈ E for each x ≠ y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. A graph is representable if and only if it is k-representable for some k [1].",
keywords = "algorithm analysis, graphs, word patterns",
author = "Magnus Halldorsson and Sergey Kitaev and Artem Pyatkin",
year = "2010",
doi = "10.1007/978-3-642-14455-4_41",
language = "English",
isbn = "978-3-642-14454-7",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "436--437",
editor = "Yuan Gao and Hanlin Lu and Shinnosuke Seki and Sheng Yu",
booktitle = "Developments in Language Theory",

}

Halldorsson, M, Kitaev, S & Pyatkin, A 2010, Graphs capturing alternations in words. in Y Gao, H Lu, S Seki & S Yu (eds), Developments in Language Theory: 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6224, pp. 436-437, 14th Conference on Dvelopments in Language Theory, London, Ontario, Canada, 17/08/10. https://doi.org/10.1007/978-3-642-14455-4_41

Graphs capturing alternations in words. / Halldorsson, Magnus; Kitaev, Sergey; Pyatkin, Artem.

Developments in Language Theory: 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings. ed. / Yuan Gao; Hanlin Lu; Shinnosuke Seki; Sheng Yu. 2010. p. 436-437 (Lecture Notes in Computer Science; Vol. 6224).

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

TY - GEN

T1 - Graphs capturing alternations in words

AU - Halldorsson, Magnus

AU - Kitaev, Sergey

AU - Pyatkin, Artem

PY - 2010

Y1 - 2010

N2 - A graph G = (V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x, y) ∈ E for each x ≠ y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. A graph is representable if and only if it is k-representable for some k [1].

AB - A graph G = (V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x, y) ∈ E for each x ≠ y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. A graph is representable if and only if it is k-representable for some k [1].

KW - algorithm analysis

KW - graphs

KW - word patterns

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/alt2p-final.pdf

U2 - 10.1007/978-3-642-14455-4_41

DO - 10.1007/978-3-642-14455-4_41

M3 - Conference contribution book

SN - 978-3-642-14454-7

T3 - Lecture Notes in Computer Science

SP - 436

EP - 437

BT - Developments in Language Theory

A2 - Gao, Yuan

A2 - Lu, Hanlin

A2 - Seki, Shinnosuke

A2 - Yu, Sheng

ER -

Halldorsson M, Kitaev S, Pyatkin A. Graphs capturing alternations in words. In Gao Y, Lu H, Seki S, Yu S, editors, Developments in Language Theory: 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings. 2010. p. 436-437. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-14455-4_41