Idealized Algol with Ground Recursion, and DPDA Equivalence | SpringerLink
Skip to main content
Springer Nature Link
Log in

Idealized Algol with Ground Recursion, and DPDA Equivalence

  • Conference paper
Automata, Languages and Programming (ICALP 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3580))

Included in the following conference series:

  • 3172 Accesses

Abstract

We prove that observational equivalence of IA 3+Y 0 (3rd-order Idealized Algol with 0th-order recursion) is equivalent to the DPDA Equivalence Problem, and hence decidable. This completes the classification of decidable fragments of Idealized Algol. We also prove that observational approximation of IA 1+Y 0 is undecidable by reducing the DPDA Containment Problem to it.

Work supported by the UK EPSRC (GR/R88861/01), European Research Training Network GAMES and St John’s College, Oxford.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ong, C.-H.L.: Observational equivalence of 3rd-order Idealized Algol is decidable. In: Proceedings of LICS, pp. 245–256 (2002)

    Google Scholar 

  2. Murawski, A.S.: On program equivalence in languages with ground-type references. In: Proceedings of LICS, pp. 108–117 (2003)

    Google Scholar 

  3. Murawski, A.S.: Games for complexity of second-order call-by-name programs. Theoretical Computer Science (to appear)

    Google Scholar 

  4. Murawski, A.S., Walukiewicz, I.: Third-order Idealized Algol with iteration is decidable. In: Sassone, V. (ed.) FOSSACS 2005. LNCS, vol. 3441, pp. 202–218. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  5. Stirling, C.: Deciding DPDA equivalence is primitive recursive. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 821–832. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  6. Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)

    MATH  Google Scholar 

  7. Abramsky, S., McCusker, G.: Linearity, sharing and state: a fully abstract game semantics for Idealized Algol with active expressions. In: O’Hearn, P.W., Tennent, R.D. (eds.) Algol-like languages, pp. 297–329. Birkhaüser, Basel (1997)

    Google Scholar 

  8. Sénizergues, G.: L(A)=L(B)? decidability results from complete formal systems. Theoretical Computer Science 251(1-2), 1–166 (2001)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computing Laboratory, Oxford University, Parks Road, Oxford, OX1 3QD, UK

    A. S. Murawski & C. -H. L. Ong

  2. CNRS, Université Bordeaux-1, 351, Cours de la Libération, 33 405, Talence, France

    I. Walukiewicz

Authors
  1. A. S. Murawski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. C. -H. L. Ong
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. I. Walukiewicz
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. CITI / Departamento de Informática, Universidade Nova de Lisboa, Portugal

    Luís Caires

  2. Dipartimento di Informatica, Sistemi e Produzione, Università di Roma “Tor Vergata”, via del Politecnico 1, 00133, Roma, Italy

    Giuseppe F. Italiano

  3. Departamento de Informatica, Universidade Nova de Lisboa, 2829-516, Caparica, Portugal

    Luís Monteiro

  4. Ecole Polytechnique, Rue de Saclay, 91128, Palaiseau Cedex, France

    Catuscia Palamidessi

  5. Computer Science Department, Google Inc. and Columbia University, 1214 Amsterdam Avenue, NY 10027, New York, USA

    Moti Yung

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Murawski, A.S., Ong, C.H.L., Walukiewicz, I. (2005). Idealized Algol with Ground Recursion, and DPDA Equivalence. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds) Automata, Languages and Programming. ICALP 2005. Lecture Notes in Computer Science, vol 3580. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11523468_74

Download citation

  • DOI: https://doi.org/10.1007/11523468_74

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-27580-0

  • Online ISBN: 978-3-540-31691-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation