A New Technique for Reachability of States in Concatenation Automata

Most Complex Deterministic Union-Free Regular Languages

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.

Cover Complexity of Finite Languages

Word Problem Languages for Free Inverse Monoids

of rank greater than 1 is not poly-context-free.

Error-Free Affine, Unitary, and Probabilistic OBDDs

A local limit property for pattern statistics in bicomponent stochastic models

Site-Directed Insertion: Decision Problems, Maximality and Minimality

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.

Finite Automata with Undirected State Graphs

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.

Two-way automata over locally finite semirings

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.

Linear-Time Limited Automata

Cycle Height of Finite Automata

State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis

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.

Properties of Right One-Way Jumping Finite Automata

On the Grammatical Complexity of Finite Languages

State complexity of unambiguous operations on deterministic finite automata

State Grammars with Stores

On the generation of 2-polyominoes

Further closure properties of input-driven pushdown automata

Forward Injective Finite Automata: Exact and Random Generation of Nonisomorphic NFAs