Yayınlanmış 1 Ocak 2021 | Sürüm v1
Dergi makalesi Açık

Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity

  • 1. Univ Perugia, Dipartimento Matemat & Informat, Perugia, Italy
  • 2. Univ Calif Santa Barbara, Dept Comp Sci, Santa Barbara, CA 93106 USA
  • 3. Univ Saskatchewan, Dept Comp Sci, Saskatoon, SK S7N 5C9, Canada

Açıklama

It is shown that for every language family that is a trio containing only semilinear languages, all bounded languages in it can be accepted by one-way deterministic reversal-bounded multicounter machines (DCM). This implies that for every semilinear trio (where these properties are effective), it is possible to decide containment, equivalence, and disjointness concerning its bounded languages. A condition is also provided for when the bounded languages in a semilinear trio coincide exactly with those accepted by DCM machines, and it is used to show that many grammar systems of finite index - such as finite-index matrix grammars (M-fin) and finite-index ETOL (ETOLfin) - have identical bounded languages as DCM.

Dosyalar

bib-d8dd00b7-1e76-4e7e-b0a8-8dd583d09243.txt

Dosyalar (233 Bytes)

Ad Boyut Hepisini indir
md5:00e1ebe14e3719e3db83f966a27638f9
233 Bytes Ön İzleme İndir