489 Works

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

Behshad Behzadi & Jean-Marc Steyaert
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.


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
Given an $n$-tape automaton $M$ with a one-way read-only head per tape which is delimited by an end marker $\$$ and a nonnegative integer $k$, we say that $M$ is weakly $k$-synchronized if for every $n$-tuple $x = (x_1, \dots, x_n)$ that is accepted, there is an accepting computation on $x$ such that no pair of input heads, neither of which is on $\$$, are more than $k$ tape cells apart at any time during...

Regular Expressions: New Results and Open Problems

Keith Ellul, Bryan Krawetz, Jeffrey Shallit & Ming-wei Wang
Regular expressions have been studied for nearly 50 years, yet many intriguing problems about their descriptive capabilities remain open. In this paper we sketch some new results and discuss what remains to be solved.

Tradeoffs Between Reliability and Conciseness of Deterministic Finite Automata

Martin Kappes & Chandra M. R. Kintala
In this paper, we propose a model for measuring the reliability of the description of a language L by a deterministic finite automaton M. Intuitively, the reliability $M$ exhibits when used for $L$ is high if the "difference" between $L$ and the language $T(M)$ accepted by $M$ is small. Using this model, we prove that the savings in the number of states between a fully reliable and a less reliable representation cannot be bounded by...

A Multiset Analogue of Cofactors

Hossein Teimoori Faal
In this paper, we first review the graph-theoretical interpretations of the determinant and cofactors of a matrix, using the idea of cycle covers of the associated digraph of that matrix. We then also review the multiset analogue of the combinatorial interpretation of the determinant based on the idea of Lydon covers. As the main result of this paper, we also give a multiset analogue of the cofactor of any entry of a matrix by giving...


Jürgen Dassow

Some Topological Properties of Rational Sets

Pierre-Cyrille Héam
In this paper we give some topological properties of rational sets. The profinite topology was first introduced for the free group by M. Hall, Jr. and by Reutenauer for the free monoid. It is the initial topology for the monoid morphisms from the free monoid into a finite discrete group. For a variety of finite groups $\V$, the pro-$\V$ topology is defined in the same way by replacing "group" by "group in $\V$" in the...

Generating all Circular Shifts by Context-Free Grammars in Chomsky Normal Form

Peter R. J. Asveld
Let $\{a_1,a_2,\ldots,a_n\}$ be an alphabet of $n$ symbols and let $C_n$ be the language of circular or cyclic shifts of the word $a_1a_2\ldots a_n$; so $C-n=\{a_1a_2\ldots a_{n-1}a_n,a_2a_3\ldots a_na_1,\ldots,a_na_1\ldots a_{n-2}a_{n-1}\}$. We discuss a few families of context-free grammars $G_n$ ($n\geq 1$) in Chomsky normal form such that $G_n$ generates $C_n$. The grammars in these families are investigated with respect to their descriptional complexity, i. e., we determine the number of nonterminal symbols $\ny(n)$ and the number...

Weighted Grammars and Automata with Threshold Interpretation

Carlos Martín-Vide, Victor Mitrana & Ralf Stiebe
We discuss a particular type of weighted grammars and automata over the partially ordered group of additive real vectors $\mathbb{R}^k$, and its subgroups $\mathbb{Z}^k$ and $\mathbb{Q}^k$, as well as over the partially ordered group of component-wise multiplicative vectors with positive rational components. Computational power of these devices is investigated in comparison with the computational power of valence grammars and blind multicounter automata. We Show that all these families are either full principal semi-AFL or full...

Registration Year

  • 2017
  • 2018
  • 2019

Resource Types

  • Text