The memory of a deque automaton is more general than a queue or two stacks; to avoid overgeneralization, we consider quasi-real-time operation. Normal forms of such automata are given. Deque languages form an AFL but not a full one. We define the characteristic deque language, CDL, which combines Dyck and AntiDyck (or FIFO) languages, and homomorphically characterizes the deque languages. The notion of deque graph, from graph theory, well represents deque computation by means of a planar hamiltonian graph on a cylinder, with edges visualizing producer-consumer relations for deque symbols. We give equivalent definitions of CDL by labelled deque graphs, by cancellation rules, and by means of shuffle and intersection of simpler languages. The labeled deque graph of a sentence generalizes traditional syntax trees. The layout of deque computations on a cylinder is remindful of 3D models used in theoretical (bio)chemistry.

Deque Languages, Automata and Planar Graphs

Crespi Reghizzi S.;San Pietro P.
2018-01-01

Abstract

The memory of a deque automaton is more general than a queue or two stacks; to avoid overgeneralization, we consider quasi-real-time operation. Normal forms of such automata are given. Deque languages form an AFL but not a full one. We define the characteristic deque language, CDL, which combines Dyck and AntiDyck (or FIFO) languages, and homomorphically characterizes the deque languages. The notion of deque graph, from graph theory, well represents deque computation by means of a planar hamiltonian graph on a cylinder, with edges visualizing producer-consumer relations for deque symbols. We give equivalent definitions of CDL by labelled deque graphs, by cancellation rules, and by means of shuffle and intersection of simpler languages. The labeled deque graph of a sentence generalizes traditional syntax trees. The layout of deque computations on a cylinder is remindful of 3D models used in theoretical (bio)chemistry.
2018
Developments in Language Theory. DLT 2018
978-3-319-98653-1
978-3-319-98654-8
File in questo prodotto:
File Dimensione Formato  
DEQUE_DLT.pdf

accesso aperto

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 165.73 kB
Formato Adobe PDF
165.73 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1122531
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact