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

Datalogisk Institut

2 Citationer (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.

Originalsprog	Engelsk
Titel	Language and automata theory and applications : 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings
Redaktører	Adrian-Horia Dediu, Jan Janoušek, Carlos Martín-Vide, Bianca Truthe
Antal sider	13
Forlag	Springer
Publikationsdato	2016
Sider	579-591
Kapitel	44
ISBN (Trykt)	978-3-319-29999-0
ISBN (Elektronisk)	978-3-319-30000-9
DOI	https://doi.org/10.1007/978-3-319-30000-9_44
Status	Udgivet - 2016
Begivenhed	International Conference, LATA 2016 - Prague, Tjekkiet Varighed: 14 mar. 2016 → 18 mar. 2016 Konferencens nummer: 10

Konference

Konference	International Conference, LATA 2016
Nummer	10
Land/Område	Tjekkiet
By	Prague
Periode	14/03/2016 → 18/03/2016

Adgang til dokumentet

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

Citationsformater

Axelsen, H. B., Holzer, M., Kutrib, M., & Malcher, A. (2016). Reversible shrinking two-pushdown automata. I A-H. Dediu, J. Janoušek, C. Martín-Vide, & B. Truthe (red.), Language and automata theory and applications: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings (s. 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. red. / Adrian-Horia Dediu; Jan Janoušek; Carlos Martín-Vide; Bianca Truthe. Springer, 2016. s. 579-591.

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Axelsen, HB, Holzer, M, Kutrib, M & Malcher, A 2016, Reversible shrinking two-pushdown automata. i A-H Dediu, J Janoušek, C Martín-Vide & B Truthe (red), Language and automata theory and applications: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings. Springer, s. 579-591, International Conference, LATA 2016, Prague, Tjekkiet, 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater