A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct.

Shibashis Guha; Ismaël Jecker; Karoliina Lehtinen; Martin Zimmermann

doi:10.4230/LIPICS.MFCS.2021.53

A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct.

Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, Martin Zimmermann

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

9 Citations (Scopus)

Abstract

We study the expressiveness and succinctness of good-for-games pushdown automata (GFG-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved based on the run constructed so far, but independently of the remainder of the input word. We prove that GFG-PDA recognise more languages than deterministic PDA (DPDA) but not all context-free languages (CFL). This class is orthogonal to unambiguous CFL. We further show that GFG-PDA can be exponentially more succinct than DPDA, while PDA can be double-exponentially more succinct than GFG-PDA. We also study GFGness in visibly pushdown automata (VPA), which enjoy better closure properties than PDA, and for which we show GFGness to be ExpTimecomplete. GFG-VPA can be exponentially more succinct than deterministic VPA, while VPA can be exponentially more succinct than GFG-VPA. Both of these lower bounds are tight. Finally, we study the complexity of resolving nondeterminism in GFG-PDA. Every GFG-PDA has a positional resolver, a function that resolves nondeterminism and that is only dependant on the current configuration. Pushdown transducers are sufficient to implement the resolvers of GFG-VPA, but not those of GFG-PDA. GFG-PDA with finite-state resolvers are determinisable.

Original language	English
Title of host publication	46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Editors	Filippo Bonchi, Simon J. Puglisi
Publication date	18 Aug 2021
Pages	53:1-53:20
Article number	53
ISBN (Electronic)	9783959772013
DOIs	https://doi.org/10.4230/LIPICS.MFCS.2021.53
Publication status	Published - 18 Aug 2021
Externally published	Yes

Bibliographical note

DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

Keywords

Good-for-games
Pushdown automata
Succintness
Synthesis

Access to Document

10.4230/LIPICS.MFCS.2021.53

https://dblp.org/rec/conf/mfcs/GuhaJL021

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

@inproceedings{7b1781acdc6445d3b5b0c5763bd0103e,

title = "A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct.",

abstract = "We study the expressiveness and succinctness of good-for-games pushdown automata (GFG-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved based on the run constructed so far, but independently of the remainder of the input word. We prove that GFG-PDA recognise more languages than deterministic PDA (DPDA) but not all context-free languages (CFL). This class is orthogonal to unambiguous CFL. We further show that GFG-PDA can be exponentially more succinct than DPDA, while PDA can be double-exponentially more succinct than GFG-PDA. We also study GFGness in visibly pushdown automata (VPA), which enjoy better closure properties than PDA, and for which we show GFGness to be ExpTimecomplete. GFG-VPA can be exponentially more succinct than deterministic VPA, while VPA can be exponentially more succinct than GFG-VPA. Both of these lower bounds are tight. Finally, we study the complexity of resolving nondeterminism in GFG-PDA. Every GFG-PDA has a positional resolver, a function that resolves nondeterminism and that is only dependant on the current configuration. Pushdown transducers are sufficient to implement the resolvers of GFG-VPA, but not those of GFG-PDA. GFG-PDA with finite-state resolvers are determinisable. ",

keywords = "Good-for-games, Pushdown automata, Succintness, Synthesis",

author = "Shibashis Guha and Isma{\"e}l Jecker and Karoliina Lehtinen and Martin Zimmermann",

note = "DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2021",

month = aug,

day = "18",

doi = "10.4230/LIPICS.MFCS.2021.53",

language = "English",

pages = "53:1--53:20",

editor = "Filippo Bonchi and Puglisi, {Simon J.}",

booktitle = "46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)",

}

A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct. / Guha, Shibashis; Jecker, Ismaël; Lehtinen, Karoliina et al.
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). ed. / Filippo Bonchi; Simon J. Puglisi. 2021. p. 53:1-53:20 53.

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

T1 - A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct.

AU - Guha, Shibashis

AU - Jecker, Ismaël

AU - Lehtinen, Karoliina

AU - Zimmermann, Martin

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2021/8/18

Y1 - 2021/8/18

N2 - We study the expressiveness and succinctness of good-for-games pushdown automata (GFG-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved based on the run constructed so far, but independently of the remainder of the input word. We prove that GFG-PDA recognise more languages than deterministic PDA (DPDA) but not all context-free languages (CFL). This class is orthogonal to unambiguous CFL. We further show that GFG-PDA can be exponentially more succinct than DPDA, while PDA can be double-exponentially more succinct than GFG-PDA. We also study GFGness in visibly pushdown automata (VPA), which enjoy better closure properties than PDA, and for which we show GFGness to be ExpTimecomplete. GFG-VPA can be exponentially more succinct than deterministic VPA, while VPA can be exponentially more succinct than GFG-VPA. Both of these lower bounds are tight. Finally, we study the complexity of resolving nondeterminism in GFG-PDA. Every GFG-PDA has a positional resolver, a function that resolves nondeterminism and that is only dependant on the current configuration. Pushdown transducers are sufficient to implement the resolvers of GFG-VPA, but not those of GFG-PDA. GFG-PDA with finite-state resolvers are determinisable.

AB - We study the expressiveness and succinctness of good-for-games pushdown automata (GFG-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved based on the run constructed so far, but independently of the remainder of the input word. We prove that GFG-PDA recognise more languages than deterministic PDA (DPDA) but not all context-free languages (CFL). This class is orthogonal to unambiguous CFL. We further show that GFG-PDA can be exponentially more succinct than DPDA, while PDA can be double-exponentially more succinct than GFG-PDA. We also study GFGness in visibly pushdown automata (VPA), which enjoy better closure properties than PDA, and for which we show GFGness to be ExpTimecomplete. GFG-VPA can be exponentially more succinct than deterministic VPA, while VPA can be exponentially more succinct than GFG-VPA. Both of these lower bounds are tight. Finally, we study the complexity of resolving nondeterminism in GFG-PDA. Every GFG-PDA has a positional resolver, a function that resolves nondeterminism and that is only dependant on the current configuration. Pushdown transducers are sufficient to implement the resolvers of GFG-VPA, but not those of GFG-PDA. GFG-PDA with finite-state resolvers are determinisable.

KW - Good-for-games

KW - Pushdown automata

KW - Succintness

KW - Synthesis

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

U2 - 10.4230/LIPICS.MFCS.2021.53

DO - 10.4230/LIPICS.MFCS.2021.53

M3 - Article in proceeding

SP - 53:1-53:20

BT - 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

A2 - Bonchi, Filippo

A2 - Puglisi, Simon J.

ER -

A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct.

Abstract

Bibliographical note

Keywords

Access to Document

AUB Link

Other files and links

Fingerprint

Best Paper Award MFCS 2021

Cite this

A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct.

Abstract

Bibliographical note

Keywords

Access to Document

AUB Link

Other files and links

Fingerprint

Prizes

Best Paper Award MFCS 2021

Cite this