489 Works

On Minimal Context-Free Insertion-Deletion Systems

Sergey Verlan
We investigate the class of context-free insertion-deletion systems. It is known that such systems are universal if the length of the inserted/deleted string is at least three. We show that if this length is bounded to two, then the obtained systems are not universal. We characterise the obtained class and we introduce a new complexity measure for insertion-deletion systems, which permits a better explanation of the obtained results.

NFA to DFA Transformation for Finite Languages over Arbitrary Alphabets

Kai Salomaa & Sheng Yu
We consider the number of states of a DFA that is equivalent to an $n$-state NFA accepting a finite language over an arbitrary alphabet. We show that, for any $n$-state NFA accepting a finite language over a $k$-letter alphabet, $n,k > 1$,there is an equivalent DFA of $O(k^{n/(\log_2 k+1)})$ states, and show that this bound is optimal in the worst case.

Non-Returning PC Grammar Systems Generate any Recursively Enumerable Language with Eight Context-Free Components

György Vaszil
We show how to generate any recursively enumerable language with a non-returning PC grammar system having eight context-free components. This is an improvement of descriptional complexity compared to the previously known construction where the number of component grammars depends on the generated language and can be arbitrarily high.

Parikh's Theorem Does Not Hold for Multiplicities

Ion Petre
We consider the question of whether the famous Parikh's Theorem holds with multiplicities i.e., for formal power series instead of languages. The strict hierarchy of algebraic, rational, recognizable and semilinear formal power series in commuting variables is proved and in this way it is established that the Parikh's Theorem does not hold with multiplicities. We also characterize the recognizable series over a product monoid giving a generalization of the Mezei's Theorem.

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,...

On the Power of P Systems with Replicated Rewriting

Vincenzo Manca, Carlos Martín-Vide & Gheorghe Păun
We continue the study of a variant of string-objects P systems recently introduced by Krishna and Rama, namely with the possibility to also replicate the strings when rewriting them. The main result of the paper solves an open problem about such P systems: the hierarchy on the number of membranes collapses, systems with six membranes characterize the recursively enumerable languages. We also investigate the power of systems with less than six membranes, in comparison with...

A Semiring-Semimodule Generalization of ω-Regular Languages I

Zoltán Ésik & Werner Kuich
We develop an algebraic theory on semiring-semimodule pairs and quemirings that is applicable to languages that contain finite and infinite words. We define finite automata over quemirings and prove two Kleene Theorems. As an application we obtain a Kleene Theorem for clock languages which are used to specify and verify real-time systems and one for languages accepted by weighted B{\"{u}}chi-automata.

Topological Properties of Forbidding-Enforcing Systems

Daniela Genova & Nataša Jonoska
Forbidding-enforcing systems (fe-systems) define classes of languages (fe-families) based on boundary conditions. We characterize f-families having not necessarily finite forbidders and prove that none of the Chomsky families of languages can be defined with an fe-system, hence, fe-systems provide a completely new way of defining classes of languages. We show that f-families map to f-families by morphic maps if and only if the morphism maps symbol to symbol. A morphism mapping e-families to e-families is...

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...

Synchronizing Non-Deterministic Finite Automata

Henk Don & Hans Zantema
In this paper, we show that every D3-directing CNFA can be mapped uniquely to a DFA with the same synchronizing word length. This implies that \v{C}ern\'y's conjecture generalizes to CNFAs and that any upper bound for the synchronizing word length of DFAs is an upper bound for the D3-directing word length of CNFAs as well. As a second consequence, for several classes of CNFAs sharper bounds are established. Finally, our results allow us to detect...

Nondeterministic State Complexity of Positional Addition

Galina Jirasková & Alexander Okhotin
Consider nondeterministic finite automata recognizing base-k positional notation of numbers. Assume that numbers are read starting from their least significant digits. It is proved that if two sets of numbers S and T are represented by nondeterministic automata of m and n states, respectively, then their sum $\{s +t \mid s\in S, t\in T\}$ is represented by a nondeterministic automaton with $2mn+2m+2n+1$ states. Moreover, this number of states is in the worst case necessary for...

Transducers with Set Output

Jurek Czyzowicz, Wojciech Fraczak & Andrzej Pelc
We consider transducers with set output, i.e., finite state machines which produce a set of output symbols (rather than a string of symbols) upon reading any input symbol. When a word consisting of input symbols is read, the union of corresponding output sets is produced. Such transducers are instrumental in some important data classification tasks, such as multi-field packet classification. Two transducers are called equivalent if they produce equal output upon reading any input word....

Languages Generated by Context-Free Grammars Extended by Type AB → BA Rules

Benedek Nagy
Derivations using branch-interchanging and language family obtained by context-free and interchange ($AB \to BA$) rules are analyzed. This language family is between the context-free and context-sensitive families. Closure properties and other properties are detailed. Only semi-linear languages can be generated in this way. Relation to partial commutations is shown.

On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata

Nutan Limaye, Meena Mahajan & Antoine Meyer
Visibly pushdown languages properly generalize regular languages and are properly contained in deterministic context-free languages. The complexity of their membership problem is equivalent to that of regular languages. However, the corresponding counting problem - computing the number of accepting paths in a visibly pushdown automaton - could be harder than counting paths in a non-deterministic finite automaton: it is only known to be in LogDCFL. We investigate the membership and counting problems for generalizations of...

Learning Unary Automata

Gregor Gramlich & Ralf Herrmann
We determine the complexity of learning problems for unary regular languages. We begin by investigating the minimum consistent dfa (resp. nfa) problem which is known not to be efficiently approximable within any polynomial, unless $P=NP$. For the case of unary dfa's, we exhibit an efficient algorithm. On the other hand, we show the intractability of the unary minimum consistent nfa problem but provide an efficient quadratic approximation for its optimization version. The VC dimension for...

Undecidability Results for Uniformly k-Limited 0L Systems

Dietmar Wätjen
In this paper we shall prove that it is undecidable whether the intersection of two uniformly $k$-limited 0L languages is empty, finite, regular, context-free, a $k$-limited or a uniformly $k$-limited language, whether the language generated by a context-free grammar is a uniformly $k$-limited 0L language or whether a uniformly $k$-limited T0L language can be generated by a context-free grammar. Furthermore, it is undecidable whether the union of two uniformly $k$-limited 0L languages is such a...

Two-Way Automata Simulations and Unary Languages

Carlo Mereghetti & Giovanni Pighizzini
One of the main problems in automata theory is evaluating the cost, in terms of states, of the optimal simulation of two-way (or also one-way) nondeterministic by two-way deterministic automata. The question, which was proposed in 1978 by W. Sakoda and M. Sipser, is still open. In this paper, we aim to give some contributions to the investigation of this problem. We show that in the unary case, namely for automata with a one-letter input...

NP Predicates Computable in the Weakest Level of the Grzegorczyck Hierarchy

Cristian Grozea
Let $(E_r){r\in N}$ be the hierarchy of Grzegorczyk. Its weakest level, $E_0$ is indeed quite weak, as it does not even contain functions such as $max(x,y)$ or $x+y$. In this paper we show that $SAT\in E_0$ by developing a technique which can be used to show the same result holds for other NP problems. Using this technique, we are able to show that also the Hamiltonian Cycle Problem is solvable in $E_0$.

Fast-Search Algorithms: New Efficient Variants of the Boyer-Moore Pattern-Matching Algorithm

Domenico Cantone & Simone Faro
We present two variants of the Boyer-Moore string matching algorithm, named Fast- Search and Forward-Fast-Search, and compare them with some of the most effective string matching algorithms, such as Horspool, Quick Search, Tuned Boyer-Moore, Reverse Factor, and Berry-Ravindran. All algorithms are compared in terms of their run-time efficiency, number of text character inspections, and number of character comparisons. It turns out that the new proposed variants, though not linear, achieve very good results especially in...

Coinductive Counting with Weighted Automata

Jan J. M. M. Rutten
A general methodology is developed to compute the solution of a wide variety of basic counting problems in a uniform way: (1) the objects to be counted are enumerated by means of an infinite weighted automaton; (2) the automaton is reduced by means of the quantitative notion of stream bisimulation; (3) the reduced automaton is used to compute an expression (in terms of stream constants and operators) that represents the stream of all counts.

Multi-Limited Simple Eco-Grammar Systems with Prescribed Teams

Dietmar Wätjen
In each derivation step of a simple eco-grammar system with prescribed teams of ter Beck [2], at most one production of every agent of a team is used. In [15], we have softened this restriction imposed upon the agents. Each agent may use a greater, but limited number of productions in every step. We have considered two different kinds of such limited eco-grammar systems with prescribed teams where the corresponding actions of the agents are...

On Monotonic Directable Nondeterministic Automata

Balázs Imreh, Csanád Imreh & Masami Ito
A finite automaton is called directable if it has an input word which takes it from every state into the same state. Directability of nondeterministic (n.d.) automata can be defined in different ways. In [7], three notions of directability, D1-, D2-, and D3-directability, are introduced. Here, for each $i = 1,2,3$, we present sharp bounds for the maximal lengths of the shortest D$i$-directing words of $n$-state monotonic D$i$-directable n. d. automata.

Small Universal Deterministic Petri Nets with Inhibitor Arcs

Artiom Alhazov, Sergiu Ivanov, Elisabeth Pelz & Sergey Verlan
This paper describes a series of small universal Petri nets with inhibitor arcs. Four parameters of descriptional complexity are considered: the number of places, transitions, inhibitor arcs, and the maximal degree of a transition. A number of techniques for reducing the values of these parameters, with special attention on places, are presented: we describe strongly universal Petri nets with 30, 21, 14, 11, and 5 places, and weakly universal Petri nets with similar parameters. We...

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.

Languages Recognized by Finite Supersoluble Groups

Oliver Carton, Jean-Éric Pin & Xaro Soler-Escrivà
In this paper, we give two descriptions of the languages recognized by finite supersoluble groups. We first show that such a language belongs to the Boolean algebra generated by the modular products of elementary commutative languages. An elementary commutative language is defined by a condition specifying the number of occurrences of each letter in its words, modulo some fixed integer. Our second characterization makes use of counting functions computed by transducers in strict triangular form.

Registration Year

  • 2017
  • 2018
  • 2019

Resource Types

  • Text