𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some Decision Problems Concerning Semilinearity and Commutation

✍ Scribed by Tero Harju; Oscar Ibarra; Juhani Karhumäki; Arto Salomaa

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
189 KB
Volume
65
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

Let M be a class of automata (in a precise sense to be defined) and M c the class obtained by augmenting each automaton in M with finitely many reversal-bounded counters. We show that if the languages defined by M are effectively semilinear, then so are the languages defined by M c , and, hence, their emptiness problem is decidable. We give examples of how this result can be used to show the decidability of certain problems concerning the equivalence of morphisms on languages. We also prove a surprising undecidability result for commutation of languages: given a fixed two-element code K, it is undecidable whether a given context-free language L commutes with K, i.e., LK ¼ KL.

📜 SIMILAR VOLUMES

Bounds and decay results for some second
Bounds and decay results for some second-order semilinear elliptic problems
✍ L. E. Payne; P. W. Schaefer; J. C. Song 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB

## Communicated by G. F. Roach The asymptotic behaviour of solutions of certain semilinear elliptic Dirichlet boundary value problems defined on a semi-infinite cylinder is investigated by means of energy arguments and maximum principles. Various hypotheses are made on the form of the semilinear t

Some problems concerning the assessment
Some problems concerning the assessment of arterial prosthetic materials
✍ Wesolowski, Sigmund A. 📂 Article 📅 1967 🏛 John Wiley and Sons 🌐 English ⚖ 214 KB

## NOTE T 'OI,. 1 (1967) \* This work was aided by grants-in-aid from t~he USPHG and the Research The two points a t which moral issues arise in reasonable clinical action are: Conncil of tbe City of New York.

On Stancu-Mühlbach Operators and Some Co
On Stancu-Mühlbach Operators and Some Connected Problems Concerning Probability Distributions
✍ J. Delacal 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 263 KB

New approximation properties concerning Beta and Stancu-Mühlbach operators are given. It is shown that both operators preserve Lipschitz constants. We also give quantitative estimates for the approximation of Bernstein, Szász, and Baskakov operators by Stancu-Mühlbach operators, as well as for the a