We establish the relation between two language recognition models that use counters and operate in real-time: Greibach's partially blind machines operating in real time (RT-PBLIND), which recognize Petri Net languages, and the consensually regular (CREG) language model of the authors. The latter is based on synchronized computational threads of a finite automaton, where at each step one thread acts as the leader and all other threads as followers. We introduce two new normal forms of RT-PBLIND machines (and Petri Nets), such that counter operations are scheduled and rarefied, and transitions are quasi-deterministic, i.e., the finite automaton obtained by eliminating counter moves is deterministic. We prove that the CREG family can simulate any normalized RT-PBLIND machine, but it also contains the non-RT-PBLIND language anbn|n>1⁎.
Counter machines, Petri Nets, and consensual computation
Crespi Reghizzi S.;San Pietro P.
2017-01-01
Abstract
We establish the relation between two language recognition models that use counters and operate in real-time: Greibach's partially blind machines operating in real time (RT-PBLIND), which recognize Petri Net languages, and the consensually regular (CREG) language model of the authors. The latter is based on synchronized computational threads of a finite automaton, where at each step one thread acts as the leader and all other threads as followers. We introduce two new normal forms of RT-PBLIND machines (and Petri Nets), such that counter operations are scheduled and rarefied, and transitions are quasi-deterministic, i.e., the finite automaton obtained by eliminating counter moves is deterministic. We prove that the CREG family can simulate any normalized RT-PBLIND machine, but it also contains the non-RT-PBLIND language anbn|n>1⁎.File | Dimensione | Formato | |
---|---|---|---|
counterLanguages.pdf
Open Access dal 16/02/2019
:
Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione
316.92 kB
Formato
Adobe PDF
|
316.92 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.