A deque automaton is a finite-state machine equipped with a deque memory tape. Such memory being more general than a queue or two stacks, we restrict consideration to quasi-real-time deque machines, for which we present useful normal forms. The closure properties of deque languages qualify them as an abstract family of languages but not a full one. The newly defined characteristic deque language CDL combines Dyck and AntiDyck (or FIFO) languages, and homomorphically characterizes the deque languages. The notion of deque graph from the graph drawing theory, well represents deque computations by means of a planar graph developed on a cylinder surface, with edges visualizing how deque symbols are inserted and removed. The drawing of deque computations on a cylinder is remindful of 3D models used in theoretical (bio)chemistry. We prove that a CDL can be defined in different ways: by a simple deque automaton, by labeled deque graphs, by cancellation rules, and by means of the shuffle and intersection of simpler languages. The labeled deque graph represents the syntax structure of a word.

Deque automata, languages, and planar graph representations

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

Abstract

A deque automaton is a finite-state machine equipped with a deque memory tape. Such memory being more general than a queue or two stacks, we restrict consideration to quasi-real-time deque machines, for which we present useful normal forms. The closure properties of deque languages qualify them as an abstract family of languages but not a full one. The newly defined characteristic deque language CDL combines Dyck and AntiDyck (or FIFO) languages, and homomorphically characterizes the deque languages. The notion of deque graph from the graph drawing theory, well represents deque computations by means of a planar graph developed on a cylinder surface, with edges visualizing how deque symbols are inserted and removed. The drawing of deque computations on a cylinder is remindful of 3D models used in theoretical (bio)chemistry. We prove that a CDL can be defined in different ways: by a simple deque automaton, by labeled deque graphs, by cancellation rules, and by means of the shuffle and intersection of simpler languages. The labeled deque graph represents the syntax structure of a word.
2020
AFL
AntiDyck
Closure properties
Cylindric planar graphs
Deque graphs
Double-ended queue
Dyck
Quasi-realtime
Queue automata
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397520301274-main.pdf

Accesso riservato

: Publisher’s version
Dimensione 482.75 kB
Formato Adobe PDF
482.75 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/1169553
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact