Pebble games over ordered structural abstractions

Yuguo He

doi:10.1007/978-3-319-55911-7_23

Pebble games over ordered structural abstractions

Yuguo He^*

^*Corresponding author for this work

School of Computer Science and Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We introduce a new notion called structural abstractions, which is particularly suitable for pebble games over finite ordered graphs. In an example, we show how to apply structural expansions and abstrac-tions in constructions and how to play pebble games over ordered struc-tural abstractions. The proof includes several observations and insights that are fundamental for any games over structural abstractions, which can be used to obtain lower bounds for a number of graph problems with order.

Original language	English
Title of host publication	Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings
Editors	Gerhard Jager, Silvia Steila, T.V. Gopal
Publisher	Springer Verlag
Pages	319-332
Number of pages	14
ISBN (Print)	9783319559100
DOIs	https://doi.org/10.1007/978-3-319-55911-7_23
Publication status	Published - 2017
Event	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 - Bern, Switzerland Duration: 20 Apr 2017 → 22 Apr 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10185 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
Country/Territory	Switzerland
City	Bern
Period	20/04/17 → 22/04/17

Keywords

Finite model theory
Pebble games
Structural abstraction

Access to Document

10.1007/978-3-319-55911-7_23

Cite this

He, Y. (2017). Pebble games over ordered structural abstractions. In G. Jager, S. Steila, & T. V. Gopal (Eds.), Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings (pp. 319-332). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10185 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-55911-7_23

He, Yuguo. / Pebble games over ordered structural abstractions. Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. editor / Gerhard Jager ; Silvia Steila ; T.V. Gopal. Springer Verlag, 2017. pp. 319-332 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{81f0b5bdb0bd4fa59f848068baadef9d,

title = "Pebble games over ordered structural abstractions",

abstract = "We introduce a new notion called structural abstractions, which is particularly suitable for pebble games over finite ordered graphs. In an example, we show how to apply structural expansions and abstrac-tions in constructions and how to play pebble games over ordered struc-tural abstractions. The proof includes several observations and insights that are fundamental for any games over structural abstractions, which can be used to obtain lower bounds for a number of graph problems with order.",

keywords = "Finite model theory, Pebble games, Structural abstraction",

author = "Yuguo He",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 ; Conference date: 20-04-2017 Through 22-04-2017",

year = "2017",

doi = "10.1007/978-3-319-55911-7_23",

language = "English",

isbn = "9783319559100",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "319--332",

editor = "Gerhard Jager and Silvia Steila and T.V. Gopal",

booktitle = "Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings",

address = "Germany",

}

He, Y 2017, Pebble games over ordered structural abstractions. in G Jager, S Steila & TV Gopal (eds), Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10185 LNCS, Springer Verlag, pp. 319-332, 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017, Bern, Switzerland, 20/04/17. https://doi.org/10.1007/978-3-319-55911-7_23

Pebble games over ordered structural abstractions. / He, Yuguo.
Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. ed. / Gerhard Jager; Silvia Steila; T.V. Gopal. Springer Verlag, 2017. p. 319-332 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10185 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Pebble games over ordered structural abstractions

AU - He, Yuguo

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - We introduce a new notion called structural abstractions, which is particularly suitable for pebble games over finite ordered graphs. In an example, we show how to apply structural expansions and abstrac-tions in constructions and how to play pebble games over ordered struc-tural abstractions. The proof includes several observations and insights that are fundamental for any games over structural abstractions, which can be used to obtain lower bounds for a number of graph problems with order.

AB - We introduce a new notion called structural abstractions, which is particularly suitable for pebble games over finite ordered graphs. In an example, we show how to apply structural expansions and abstrac-tions in constructions and how to play pebble games over ordered struc-tural abstractions. The proof includes several observations and insights that are fundamental for any games over structural abstractions, which can be used to obtain lower bounds for a number of graph problems with order.

KW - Finite model theory

KW - Pebble games

KW - Structural abstraction

UR - http://www.scopus.com/inward/record.url?scp=85018371797&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-55911-7_23

DO - 10.1007/978-3-319-55911-7_23

M3 - Conference contribution

AN - SCOPUS:85018371797

SN - 9783319559100

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 319

EP - 332

BT - Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings

A2 - Jager, Gerhard

A2 - Steila, Silvia

A2 - Gopal, T.V.

PB - Springer Verlag

T2 - 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017

Y2 - 20 April 2017 through 22 April 2017

ER -

He Y. Pebble games over ordered structural abstractions. In Jager G, Steila S, Gopal TV, editors, Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. Springer Verlag. 2017. p. 319-332. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-55911-7_23

Pebble games over ordered structural abstractions

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this