A Comparison of the Descriptional Complexity of Classes of Limited Lindenmayer Systems - Part II

Ronny Harbich & Bianca Truthe
We study the descriptional complexity of various limited Lindenmayer systems. We show differences in the descriptional complexity between variants, where one variant generates more languages than another one. The used measures of descriptional complexity are the number of rules and the number of symbols. The results are summarized graphically at the end of this article. The present paper is a sequel to the paper \emph{A Comparison of the Descriptional Complexity of Classes of Limited Lindenmayer...

Injectivity of the Quotient h\g of two Morphisms and Ambiguity of Linear Grammars

Paavo Turakainen
From a linear context-free grammar simulating an arbitrary instance $(\varphi_1,\varphi_2)$ of the Post correspondence problem PCP we easily construct two nonerasing morphisms $h$ and $g$ with $h$ length-duplicating such that the instance $(h,g)$ of PCP has no solution but $(\varphi_1,\varphi_2)$ possesses a solution if and only if the quotient operation $h\g$ is not injective on its domain. Hence, the undecidability of the injectivity problem follows.

Groups and Automata: a Perfect Match

Pedro V. Silva
We present a personal perspective, inspired by our own research experience, of the interaction between group theory and automata theory: from Benois' Theorem to Stallings' automata, from hyperbolic to automatic groups, not forgetting the exotic automaton groups.

What is a Complex Regular Language?

Cezar Câmpeanu
If two regular languages have both the state complexity equal to $n$, how can we further say that one of them is more complex than the other one? In other words, when can we say that a regular language is complex? In this paper, we try to answer this question, by proposing a few possible measures that we can use to quantify the relative complexity of regular languages and compare all these proposals with the...

Semiring Structures of Some Classes of Hypercodes

Zhixi Wang, Feixiang Liang, Yong He & Di Yang
An idempotent semiring is called an incline if it satisfies the identity $1 + x=x$. The class of inclines is a variety of semirings with the variety of c-semirings as a subvariety. Let $A^*$ be the free monoid on an alphabet $A$, and let $\leq_h$ be the embedding order on $A^*$. Then, as the algebra of independent subsets of the ordered monoid $(A^*,\leq_h)$, the set $H(A)$ of hypercodes on $A$ forms a free incline. Furthermore,...

The Role of the Direction in Tissue P Systems with Cell Separation

Luis F. Macías-Ramos, Miguel A. Martínez-del-Amor, Mario J. Pérez-Jiménez, Augustin Riscos-Núñez & Luis Valencia-Cabrera
Tissue P systems with cell separation where the communication among cells is performed by means of symport and antiport rules are able to efficiently solve computationally hard problems in a feasible time by a space-time trade off. Symport and antiport rules formally capture the cases where a number of chemical substances pass through a membrane at the same time, with the help of each other, either in the same direction (symport) or in opposite directions...

The Transformation Distance Problem Revisited

Evolution acts in several ways on biological sequences: either by mutating an element, or by inserting, deleting or copying a segment of the sequence. Varr{\'{e}} et al. [13] defined a transformation distance for the sequences, in which the evolutionary operations are copy, reverse copy and insertion of a segment. They also proposed an algorithm to calculate the transformation distance. This algorithm is $O((n+m)^4)$ in time and $O((n+m)^4)$ in space, where $n$ is the size target...

Hajós Factorizations of Cyclic Groups – A Simpler Proof of a Characterization

Clelia De Felice
A pair $(T, R)$ of subsets of a finite abelian group $G$ is a factorization of $G$ if $G$ is the direct sum of $T$ and $R$. A class of factorizations of finite cyclic groups were described by Haj{\'{o}}s and a new characterization of these factorizations arose in the framework of the theory of variable-length codes. In this note we will give a simpler proof of this characterization.

A New Measure of Asymmetry of Binary Words

Olexandr Ravsky
A binary word is symmetric if it is a palindrome or an antipalindrome. We define a new measure of asymmetry of a binary word equal to the minimal number of letters of the word whose deleting from the word yields a symmetric word and obtain upper and lower estimations of this measure.

Descriptional Complexity of Deterministic Finite Automata with Multiple Initial States

Martin Kappes
We study the descriptional complexity of finite automata with multiple initial states and a deterministic transition function. The model is compared to ordinary deterministic and nondeterministic finite automata. It allows to use nondeterminism in practical applications and still provides in some cases exponential savings in the number of states compared to the smallest deterministic finite automaton. Using another acceptance criterion, even exponential savings over nondeterministic finite automata are achievable while the implementation remains easy.

On Recursive and Non-Recursive Trade-Offs Between Finite-Turn Pushdown Automata

Andreas Malcher
It is shown that between one-turn pushdown automata (1-turn PDAs) and deterministic finite automata (DFAs) there will be savings concerning the size of description not bounded by any recursive function, so-called non-recursive trade-offs. Considering the number of turns of the stack height as a consumable resource of PDAs, the existence of non-recursive trade-offs between PDAs performing $k+1$ turns and $k$ turns for $k\geq 1$ is proven. Furthermore, non-recursive trade-offs are shown between arbitrary PDAs and...

On Lindenmayer Systems with Dynamic Control of Parallelism

Henning Bordihn & György Vaszil
M-rate 0L systems are interactionless Lindenmayer systems together with a function assigning to every string a set of multisets of productions that may be applied simultaneously to the string. Also tabled and extended variants of M-rate 0L systems are considered. Some results concerning the computational power of these systems are presented supplementing those contained in~\cite{CsuFreSbu06}.

Asymptotically Optimal Low-Cost Solid Codes

Helmut Jürgensen, Stavros Konstantinidis & Nguyen Huong Lâm
A new construction of solid codes is introduced. With this construction one obtains classes of solid codes which are asymptotically optimal in terms of information rate and which have low-cost systematic encoding and decoding algorithms. The construction uses a new result on the asymptotic average length of maximal runs in words.

Editorial

Diane Donovan, Costas Iliopoulos & Mirka Miller

Ranking and Unranking of Lexicographically Ordered Words: An Average-Case Analysis

Jens Liebehenschel
We consider all words of length $n$ of a formal language. If these words are arranged according to the lexicographical order, then ranking means to determine the position of a word of the language. Unranking is the inverse operation of ranking. For a given formal language we compute the average length of the shortest prefix of a word to be read to determine its position, if the word is read from left to right. The...

Gröbner Bases and the Defining Polynomial of a Context-Free Grammar Generating Function

Alois Panholzer
We consider proper algebraic systems as defined in [7] and reprove via Gr{\"{o}}bner bases algorithms that the quasiregular solution of such a system is algebraic. In this context, the effective primary decomposition of a polynomial ideal resp. the effective decomposition of an affine algebraic variety into irreducible components are alternatives to the Kuich-Salomaa elimination algorithm described in [7]. Both here applied decom- positions are based on the construction of a Gr{\"{o}}bner basis of an elimination...

P Systems with Conditional Communication Rules Assigned to Membranes

Rudolf Freund & Marion Oswald
We introduce a variant of purely communicating membrane systems where the rules are directly assigned to the membranes and not to the regions as this is usually observed in the area of membrane systems. Multisets of promotors and inhibitors inside and outside the membrane control the application of rules assigned to a membrane. For the application of rules leading from one configuration of the system to the succeeding configuration we consider a sequential model and...

Weak Synchronization and Synchronizability of Multi-Tape Pushdown Automata and Turing Machines

Oscar H. Ibarra & Nicholas Q. Tran

• 2017
30
• 2018
454
• 2019
5

• Text
487