Uniform Distributed Pushdown Automata Systems.

Arroyo Montoro, Fernando and Castellanos Peñuela, Juan Bautista and Mitrana, Víctor (2012). Uniform Distributed Pushdown Automata Systems.. In: "14th International Workshop, DCFS 2012 Descriptional Complexity of Formal Systems.", 23/07/2012 - 25/07/2012, Braga, Portugal. ISBN 0302-9743. pp. 64-75. https://doi.org/10.1007/978-3-642-31623-4_5.

Description

Title: Uniform Distributed Pushdown Automata Systems.
Author/s:
  • Arroyo Montoro, Fernando
  • Castellanos Peñuela, Juan Bautista
  • Mitrana, Víctor
Item Type: Presentation at Congress or Conference (Article)
Event Title: 14th International Workshop, DCFS 2012 Descriptional Complexity of Formal Systems.
Event Dates: 23/07/2012 - 25/07/2012
Event Location: Braga, Portugal
Title of Book: DCFS 2012 Proceedings en Lecture Notes in Computer Science
Date: 2012
ISBN: 0302-9743
Volume: 7386
Subjects:
Faculty: E.U. de Informática (UPM)
Department: Lenguajes, Proyectos y Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (750kB) | Preview

Abstract

We consider here uniform distributed pushdown automata systems (UDPAS), namely distributed pushdown automata systems having all components identical pushdown automata. We consider here just a single protocol for activating/deactivating components, namely a component stays active as long as it can perform moves, as well as two ways of accepting the input word: by empty stacks (all components have empty stacks) or by final states (all components are in final states), when the input word is completely read. We mainly investigate the computational power of UDPAS accepting by empty stacks and a few decidability and closure properties of the families of languages they define. Some directions for further work and open problems are also discussed.

More information

Item ID: 19733
DC Identifier: http://oa.upm.es/19733/
OAI Identifier: oai:oa.upm.es:19733
DOI: 10.1007/978-3-642-31623-4_5
Deposited by: Memoria Investigacion
Deposited on: 10 Mar 2014 13:50
Last Modified: 21 Apr 2016 21:02
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM