DCFS 2018 Accepted Papers with Abstracts

Abstract: We present a new technique for demonstrating the reachability of states in deterministic finite automata representing the concatenation of two languages. Such demonstrations are a necessary step in establishing the state complexity of the concatenation of two languages, and thus in establishing the state complexity of concatenation as an operation. Typically, ad-hoc induction arguments are used to show particular states are reachable in concatenation automata. We prove some results that seem to capture the essence of many of these induction arguments. Using these results, reachability proofs in concatenation automata can often be done more simply and without using induction directly.

Abstract: A regular language L is union-free if it can be represented by a regular expression without the union operation.
A union-free language is deterministic if it can be accepted by a deterministic one-cycle-free-path finite automaton; this is an automaton which has one final state and exactly one cycle-free path from any state to the final state.
Jiraskova and Masopust proved that the state complexities of the basic operations reversal, star, product, and boolean operations in deterministic union-free languages are exactly the same as those in the class of all regular languages.
To prove that the bounds are met they used five types of automata, involving eight types of transformations of the set of states of the automata.
We show that for each n >= 3 there exists one ternary witness of state complexity n that meets the bound for reversal and product.
Moreover, the restrictions of this witness to binary alphabets meet the bounds for star and boolean operations.
We also show that the tight upper bounds on the state complexity of binary operations that take arguments over different alphabets are the same as those for arbitrary regular languages.
Furthermore, we prove that the maximal syntactic semigroup of a union-free language has n^n elements, as in the case of regular languages, and
that the maximal state complexities of atoms of union-free languages are the same as those for regular languages.
Finally, we prove that there exists a most complex union-free language that meets the bounds for all these complexity measures.
Altogether this proves that the complexity measures above cannot distinguish union-free languages from regular languages.

Abstract: We consider the notion of cover complexity of finite languages on three different levels of abstraction. For arbitrary cover complexity measures, we give a characterisation of the situations in which they collapse to a bounded complexity measure. Moreover, we show for a restricted class of context-free grammars that its grammatical cover complexity measure w.r.t. a finite language L is unbounded and that the cover complexity of L can be computed from the exact complexities of a finite number of covers L' of L. We also investigate upper and lower bounds on the grammatical cover complexity of the language operations intersection, union, and concatenation on finite languages for several different types of context-free grammars.

Abstract: This paper considers the word problem for free inverse monoids of finite rank from a language theory perspective. It is shown that no free inverse monoid has context-free word problem; that the word problem of the free inverse monoid of rank 1 is both 2-context-free (an intersection of two context-free languages) and ET0L; that the co-word problem of the free inverse monoid of rank 1 is context-free; and that the word problem of a free inverse monoid
of rank greater than 1 is not poly-context-free.

Abstract: We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results by considering the automata versions of these models.

Abstract: We present a non-Gaussian local limit theorem for the number of occurrences of a given symbol in a word of length $n$ generated at random. The stochastic model for the random generation is defined by a rational formal series with non-negative real coefficients. The result yields a local limit towards a uniform density function and holds under the assumption that the formal series defining the model is recognized by a weighted finite state automaton with two primitive components having equal dominant eigenvalue.

Abstract: Site-directed insertion is an overlapping insertion
operation that can be viewed as analogous to the
overlap assembly or chop operations that concatenate
strings by overlapping a suffix and a prefix of the
argument strings.
We consider decision problems and language equations involving
site-directed insertion. By relying on the tools provided
by semantic shuffle on trajectories we show that one variable
equations involving site-directed insertion and regular constants
can be solved. We consider also maximal and minimal variants
of the site-directed insertion operation.

Abstract: We investigate finite automata whose state graphs are undirected.
This means that for any transition from state p to q consuming
some letter a from the input there exists a symmetric transition
from state q to p consuming a letter a as well. So, the corresponding
language families are subregular and, in particular in the
deterministic case, subreversible. In detail, we study the
operational descriptional complexity of deterministic and
nondeterministic undirected finite automata. To this end, the
different types of automata on alphabets with few letters are
characterized. Then the operational state complexity of the
Boolean operations as well as the operations concatenation and
iteration is investigated, where tight upper and lower bounds
are derived for unary as well as arbitrary alphabets under the
condition that the corresponding language classes are closed
under the operation considered.

Abstract: Finite two-way automata have been considered since the dawn
of automata theory. It was proven at this time that this model is equivalent
to finite one-way automata. Nevertheless, two-way transducers or weighted
automata are in general more powerful than one-way ones. We show that two-
way automata over locally finite semirings may have undefined behaviour. We
prove that it is decidable whether this behaviour is defined, and, if it is, we
show that two-way automata over locally finite semirings are equivalent to
one-way automata.

Abstract: The time complexity of 1-limited automata is investigated from a descriptional complexity point of view. Though the model recognizes regular languages only, it may use quadratic time in the input length. We show that, with a polynomial increase of the size, each 1-limited automaton can be transformed into an halting linear-time equivalent one. Furthermore the construction preserves determinism. We also obtain polynomial transformations into related models, including weight-reducing Hennie machines and we show exponential gaps for converse transformations in the deterministic case.

Abstract: A nondeterministic finite automaton (NFA) A has cycle height K if any computation of A can visit at most K cycles, and A has finite cycle height if it has cycle height K for some K. We give a polynomial time algorithm to decide whether an NFA has finite cycle height and, in the positive case, to compute its optimal cycle height. Nondeterministic finite automata of finite cycle height recognize the polynomial density regular languages. We give a polynomial time algorithm that, for a deterministic finite automaton A with finite cycle height, computes the degree of the polynomial that gives the density of the language of A.

Abstract: The linear space hypothesis is a practical working hypothesis, which originally states the insolvability of a restricted 2CNF Boolean formula satisfiability problem (2SAT$_3$) with respect to the number of Boolean variables. From this hypothesis, it follows that the degree-3 directed graph connectivity problem (3DSTCON) parameterized by the number of vertices in a given graph cannot belong to PsubLIN (characterized by polynomial-time, sub-linear space deterministic Turing machines).
This hypothesis immediately implies L \neq NL and it was used as a solid foundation to obtain new lower bounds of the computational complexity of various NL search and NL optimization problems.
The state complexity of transformation refers to the cost of converting one type of finite automata to another type, where the cost is measured in terms of the increase of the number of inner states of the automata from the original number.
We relate the linear space hypothesis to the state complexity of transforming restricted 2-way nondeterministic finite automata to equivalent 2-way alternating finite automata having narrow computation trees.
For this purpose, we present state complexity characterizations of 3DSTCON and PsubLIN. We further characterize a non-uniform version of the linear space hypothesis in terms of state complexity of transformation.

Abstract: Right one-way jumping finite automata (ROWJFAs), were recently introduced in [H. Chigahara, S. Z. Fazekas, A. Yamamura: One-Way Jumping Finite Automata, Internat. J. Found. Comput. Sci., 27(3), 2016] and are jumping automata that process the input in a dis- continuous way with the restriction that the input head reads determinis- tically from left-to-right starting from the leftmost letter in the input and when it reaches the end of the input word, it returns to the beginning and continues the computation. We solve most of the open problems of these devices. In particular, we characterize the family of permutation closed languages accepted by ROWJFAs in terms of Myhill-Nerode equivalence classes. Using this, we investigate closure and non-closure properties as well as inclusion relations to other language families. We also give more characterizations of languages accepted by ROWJFAs for some interesting cases.

Abstract: We study the grammatical production complexity of finite languages w.r.t. (i) different interpretations of approximation, i.e., equivalence, cover, and scattered cover, and (ii) whether the underlying grammar generates a finite or infinite language. In case the generated language is infinite, the intersection with all words up to a certain length has to be considered in order to obtain the finite language under consideration. This way, we obtain six different measures for regular, linear context-free, and context-free grammars. We compare these measures according to the taxonomy introduced in [J. Dassow, Gh. Păun: Regulated Rewriting in Formal Language Theory, 1989] with each other by fixing the grammar type and varying the complexity measure and by fixing the complexity measure and varying the grammar type. In both of these cases, we develop an almost complete picture, which gives new and interesting insights into the old topic of grammatical production complexity.

Abstract: The paper determines the number of states in a deterministic finite automaton (DFA) necessary to represent "unambiguous" variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m-state and an n-state DFA, the state complexity is mn-1; for the unambiguous concatenation, it is m2^{n-1}-2^{n-2}, and for the unambiguous star, the state complexity function is 3/8 2^n+1, and all the witness languages are defined over a binary alphabet. In the case of a unary alphabet, disjoint union requires up to 1/2 mn states, unambiguous concatenation has state complexity m+n-2, and unambiguous star requires n-2 states in the worst case.

Abstract: State grammars are context-free grammars where the productions have states associated with them, and can only be applied to a nonterminal if the current state matches the state in the production. Once states are added to grammars, it is natural to add various stores, similar to machine models. With such extensions, productions can only be applied if both the state and the value read from each store matches between the current sentential form and the production. Here, generative capacity results are presented for different derivation modes, with and without additional stores. In particular, with the standard derivation relation, it is shown that adding reversal-bounded counters does not increase the capacity, and states are enough. Also, state grammars with reversal-bounded counters that operate using leftmost derivations are shown to coincide with languages accepted by one-way machines with a pushdown and reversal-bounded counters, and these are surprisingly shown to be strictly weaker than state grammars with the normal derivation relation (and no counters). Complexity results of some decision problems involving state grammars with counters are also studied.

Abstract: The class of 2-polyominoes contains all polyominoes $P$ having the property that for any integer $i$, the first $i$ columns of $P$ consist of at most 2 polyominoes. We provide a decomposition that allows us to exploit suitable discrete dynamical systems to define an algorithm for generating all 2-polyominoes of area $n$ in constant amortized time and in space $O(n)$.

Abstract: The paper investigates the closure of the language family defined by input-driven pushdown automata (IDPDA) under the following operations: insertion ins(L, K)=\{xyz | xz \in L, y \in K\}, deletion del(L, K)=\{xz | xyz \in L, y \in K\}, square root \sqrt{L}=\{w | ww \in L\}, and the first half 1/2 L=\{u | \exists v: |u|=|v|, uv \in L\}. For K and L recognized by nondeterministic IDPDA, with m and with n states, respectively, insertion requires mn+2m states, as long as K is well-nested; deletion is representable with 2n states, for well-nested K; square root requires n^3-O(n^2) states, for well-nested L; the well-nested subset of the first half is representable with 2^{O(n^2)} states. Without the well-nestedness constraints, non-closure is established in each case.

Abstract: We define the class of forward injective finite automata (FIFA) and study some of their properties. Each FIFA has an unique canonical representation up to isomorphism. Using this representation an enumeration is given and an efficient uniform random generator is presented. We provide a conversion algorithm from a nondeterministic finite automaton or regular expression into an equivalent FIFA. Finally, we present some experimental results comparing the size of FIFA with other equivalent automata.