ML p(r)ior | Unrestricted State Complexity of Binary Operations on Regular Languages

Unrestricted State Complexity of Binary Operations on Regular Languages

2016-02-03
1602.01387 | cs.FL
I study the state complexity of binary operations on regular languages over different alphabets. It is well known that if $L'_m$ and $L_n$ are languages restricted to be over the same alphabet, with $m$ and $n$ quotients, respectively, the state complexity of any binary boolean operation on $L'_m$ and $L_n$ is $mn$, and that of the product (concatenation) is $(m-1)2^n +2^{n-1}$. In contrast to this, I show that if $L'_m$ and $L_n$ are over their own different alphabets, the state complexity of union and symmetric difference is $mn+m+n+1$, that of intersection is $mn$, that of difference is $mn+m$, and that of the product is $m2^n+2^{n-1}$.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2019-03-08

Several insertion operations are studied applied to languages accepted by one-way and two-way determ… show more
PDF

Highlights - Most important sentences from the article

2019-03-10

The Thue-Morse set is the set of those nonnegative integers whose binary expansions have an even num… show more
PDF

Highlights - Most important sentences from the article

2017-08-21
1708.06228 | cs.FL

Let b be an integer strictly greater than 1. Each set of nonnegative integers is represented in base… show more
PDF

Highlights - Most important sentences from the article

2018-06-12

In a simple pattern matching problem one has a pattern $w$ and a text $t$, which are words over a fi… show more
PDF

Highlights - Most important sentences from the article

2018-06-22
1806.08476 | cs.FL

The state complexity of the result of a regular operation is often positively correlated with the nu… show more
PDF

Highlights - Most important sentences from the article

2018-07-02

A monster is an automaton in which every function from states to states is represented by at least o… show more
PDF

Highlights - Most important sentences from the article

2017-10-16

The \emph{state complexity} of a regular language $L_m$ is the number $m$ of states in a minimal det… show more
PDF

Highlights - Most important sentences from the article

2013-01-21

The article defines and studies the genus of finite state deterministic automata (FSA) and regular l… show more
PDF

Highlights - Most important sentences from the article

2017-03-18
1703.06356 | cs.FL

We study extremal and algorithmic questions of subset and careful synchronization in monotonic autom… show more
PDF

Highlights - Most important sentences from the article

2015-06-01
1506.00482 | cs.LO

This work is concerned with regular languages defined over large alphabets, either infinite or just … show more
PDF

Highlights - Most important sentences from the article

2016-07-01
1607.00259 | cs.CC

The notion of Online State Complexity, introduced by Karp in 1967, quantifies the amount of states r… show more
PDF

Highlights - Most important sentences from the article

2013-04-21
1304.5714 | cs.FL

We give a forbidden pattern characterization for the class of generalized definite languages, show t… show more
PDF

Highlights - Most important sentences from the article

2017-02-14

In a recent paper we analyzed the space complexity of streaming algorithms whose goal is to decide m… show more
PDF

Highlights - Most important sentences from the article

2015-05-07
1505.01662 | cs.FL

Hereditarily finite (HF) set theory provides a standard universe of sets, but with no infinite sets.… show more
PDF

Highlights - Most important sentences from the article

2016-02-13

This paper introduces time window temporal logic (TWTL), a rich expressivity language for describing… show more
PDF

Highlights - Most important sentences from the article

2017-03-15
1703.05011 | cs.SY

Complexity analysis becomes a common task in supervisory control. However, many results of interest … show more
PDF

Highlights - Most important sentences from the article

2017-03-15
1703.05016 | cs.SY

The infimal prefix-closed, controllable and observable superlanguage plays an essential role in the … show more