Reversible shrinking two-pushdown automata

Holger Bock Axelsen; Markus Holzer; Martin Kutrib; Andreas Malcher

doi:10.1007/978-3-319-30000-9_44

Reversible shrinking two-pushdown automata

Holger Bock Axelsen, Markus Holzer, Martin Kutrib, Andreas Malcher

Department of Computer Science

2 Citations (Scopus)

Abstract

The deterministic shrinking two-pushdown automata characterize the deterministic growing context-sensitive languages, known to be the Church-Rosser languages. Here, we initiate the investigation of reversible two-pushdown automata, RTPDAs, in particular the shrinking variant. We show that as with the deterministic version, shrinking and length-reducing RTPDAs are equivalent. We then give a separation of the deterministic and reversible shrinking two-pushdown automata, and prove that these are incomparable with the (deterministic) context-free languages. We further show that the properties of emptiness, (in)finiteness, universality, inclusion, equivalence, regularity, and context-freeness are not even semi-decidable for shrinking RTPDAs.

Original language	English
Title of host publication	Language and automata theory and applications : 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings
Editors	Adrian-Horia Dediu, Jan Janoušek, Carlos Martín-Vide, Bianca Truthe
Number of pages	13
Publisher	Springer
Publication date	2016
Pages	579-591
Chapter	44
ISBN (Print)	978-3-319-29999-0
ISBN (Electronic)	978-3-319-30000-9
DOIs	https://doi.org/10.1007/978-3-319-30000-9_44
Publication status	Published - 2016
Event	International Conference, LATA 2016 - Prague, Czech Republic Duration: 14 Mar 2016 → 18 Mar 2016 Conference number: 10

Conference

Conference	International Conference, LATA 2016
Number	10
Country/Territory	Czech Republic
City	Prague
Period	14/03/2016 → 18/03/2016

Access to Document

10.1007/978-3-319-30000-9_44

Cite this

Axelsen, H. B., Holzer, M., Kutrib, M., & Malcher, A. (2016). Reversible shrinking two-pushdown automata. In A-H. Dediu, J. Janoušek, C. Martín-Vide, & B. Truthe (Eds.), Language and automata theory and applications: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings (pp. 579-591). Springer. https://doi.org/10.1007/978-3-319-30000-9_44

Reversible shrinking two-pushdown automata. / Axelsen, Holger Bock; Holzer, Markus; Kutrib, Martin et al.

Language and automata theory and applications: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings. ed. / Adrian-Horia Dediu; Jan Janoušek; Carlos Martín-Vide; Bianca Truthe. Springer, 2016. p. 579-591.

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

Axelsen, HB, Holzer, M, Kutrib, M & Malcher, A 2016, Reversible shrinking two-pushdown automata. in A-H Dediu, J Janoušek, C Martín-Vide & B Truthe (eds), Language and automata theory and applications: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings. Springer, pp. 579-591, International Conference, LATA 2016, Prague, Czech Republic, 14/03/2016. https://doi.org/10.1007/978-3-319-30000-9_44

@inproceedings{8aff3423ec1b4472bbe8f5afe3e3d471,

title = "Reversible shrinking two-pushdown automata",

abstract = "The deterministic shrinking two-pushdown automata characterize the deterministic growing context-sensitive languages, known to be the Church-Rosser languages. Here, we initiate the investigation of reversible two-pushdown automata, RTPDAs, in particular the shrinking variant. We show that as with the deterministic version, shrinking and length-reducing RTPDAs are equivalent. We then give a separation of the deterministic and reversible shrinking two-pushdown automata, and prove that these are incomparable with the (deterministic) context-free languages. We further show that the properties of emptiness, (in)finiteness, universality, inclusion, equivalence, regularity, and context-freeness are not even semi-decidable for shrinking RTPDAs.",

author = "Axelsen, {Holger Bock} and Markus Holzer and Martin Kutrib and Andreas Malcher",

year = "2016",

doi = "10.1007/978-3-319-30000-9_44",

language = "English",

isbn = "978-3-319-29999-0",

pages = "579--591",

editor = "Adrian-Horia Dediu and Jan Janou{\v s}ek and Carlos Mart{\'i}n-Vide and Bianca Truthe",

booktitle = "Language and automata theory and applications",

publisher = "Springer",

note = "International Conference, LATA 2016 ; Conference date: 14-03-2016 Through 18-03-2016",

}

TY - GEN

T1 - Reversible shrinking two-pushdown automata

AU - Axelsen, Holger Bock

AU - Holzer, Markus

AU - Kutrib, Martin

AU - Malcher, Andreas

N1 - Conference code: 10

PY - 2016

Y1 - 2016

N2 - The deterministic shrinking two-pushdown automata characterize the deterministic growing context-sensitive languages, known to be the Church-Rosser languages. Here, we initiate the investigation of reversible two-pushdown automata, RTPDAs, in particular the shrinking variant. We show that as with the deterministic version, shrinking and length-reducing RTPDAs are equivalent. We then give a separation of the deterministic and reversible shrinking two-pushdown automata, and prove that these are incomparable with the (deterministic) context-free languages. We further show that the properties of emptiness, (in)finiteness, universality, inclusion, equivalence, regularity, and context-freeness are not even semi-decidable for shrinking RTPDAs.

AB - The deterministic shrinking two-pushdown automata characterize the deterministic growing context-sensitive languages, known to be the Church-Rosser languages. Here, we initiate the investigation of reversible two-pushdown automata, RTPDAs, in particular the shrinking variant. We show that as with the deterministic version, shrinking and length-reducing RTPDAs are equivalent. We then give a separation of the deterministic and reversible shrinking two-pushdown automata, and prove that these are incomparable with the (deterministic) context-free languages. We further show that the properties of emptiness, (in)finiteness, universality, inclusion, equivalence, regularity, and context-freeness are not even semi-decidable for shrinking RTPDAs.

U2 - 10.1007/978-3-319-30000-9_44

DO - 10.1007/978-3-319-30000-9_44

M3 - Article in proceedings

SN - 978-3-319-29999-0

SP - 579

EP - 591

BT - Language and automata theory and applications

A2 - Dediu, Adrian-Horia

A2 - Janoušek, Jan

A2 - Martín-Vide, Carlos

A2 - Truthe, Bianca

PB - Springer

T2 - International Conference, LATA 2016

Y2 - 14 March 2016 through 18 March 2016

ER -

Reversible shrinking two-pushdown automata

Abstract

Conference

Access to Document

Fingerprint

Cite this