Conjunctive grammars, cellular automata and logic - GREYC amacc Access content directly
Conference Papers Year : 2021

Conjunctive grammars, cellular automata and logic

Abstract

The expressive power of the class Conj of conjunctive languages, i.e. languages generated by the conjunctive grammars of Okhotin, is largely unknown, while its restriction LinConj to linear conjunctive grammars equals the class of languages recognized by real-time one-way one-dimensional cellular automata. We prove two weakened versions of the open question Conj ⊆? RealTimeCA: 1) it is true for unary languages; 2) Conj ⊆ RealTime2OCA, i.e. any conjunctive language is recognized by a real-time one-way two-dimensional cellular automaton. Interestingly, we express the rules of a conjunctive grammar in two Horn logics, which exactly characterize the complexity classes RealTimeCA and RealTime2OCA.
Fichier principal
Vignette du fichier
OASIcs-AUTOMATA-2021-8.pdf (811.13 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive

Dates and versions

hal-03167529 , version 1 (12-03-2021)
hal-03167529 , version 2 (09-11-2022)

Licence

Attribution

Identifiers

Cite

Théo Grente, Etienne Grandjean. Conjunctive grammars, cellular automata and logic. AUTOMATA, Jul 2021, Marseille, France. ⟨10.4230/OASIcs.AUTOMATA.2021.8⟩. ⟨hal-03167529v2⟩
118 View
97 Download

Altmetric

Share

Gmail Facebook X LinkedIn More