Results 271 to 280 of about 948,220 (309)
Some of the next articles are maybe not open access.
Undecidability of state complexity
International Journal of Computer Mathematics, 2013We consider the state complexity of compositions of regularity-preserving language operations. As our main result, we establish that determining the state complexity of an operation composed just from intersections and marked concatenations is undecidable. The proof relies on the undecidability of Hilbert's Tenth Problem.
Kai Salomaa
exaly +2 more sources
International Journal of Foundations of Computer Science, 2016
It is well known that the resulting language obtained by inserting a regular language to a regular language is regular. We study the nondeterministic and deterministic state complexity of the insertion operation. Given two incomplete DFAs of sizes m and n, we give an upper bound (m+2)·2mn−m−1·3m and find a lower bound for an asymp-totically tight ...
Yo-Sub Han +3 more
openaire +2 more sources
It is well known that the resulting language obtained by inserting a regular language to a regular language is regular. We study the nondeterministic and deterministic state complexity of the insertion operation. Given two incomplete DFAs of sizes m and n, we give an upper bound (m+2)·2mn−m−1·3m and find a lower bound for an asymp-totically tight ...
Yo-Sub Han +3 more
openaire +2 more sources
STATE COMPLEXITY AND APPROXIMATION
International Journal of Foundations of Computer Science, 2012We discuss a number of essential questions concerning the state complexity research. The questions include why many basic problems were not studied earlier, whether there is a general algorithm for state complexity of combined operations, and whether there is a new and effective approach in this area of research.
Yuan Gao 0001, Sheng Yu 0001
openaire +1 more source
STATE COMPLEXITY OF CODE OPERATORS
International Journal of Foundations of Computer Science, 2011We consider five operators on a regular language. Each of them is a tool for constructing a code (respectively prefix, suffix, bifix, infix) and a hypercode out of a given regular language. We give the precise values of the (deterministic) state complexity of these operators: over a constant-size alphabet for the first four of them and over a quadratic-
Pribavkina E., Rodaro E.
openaire +2 more sources
2014
It is well known that the language obtained by deleting an arbitrary language from a regular language is regular. We give an upper bound for the state complexity of deleting an arbitrary language from a regular language and a matching lower bound. We show that the state complexity of deletion is n ·2 n − 1 (respectively, \((n + \frac{1}{2}) \cdot 2^n -
Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
openaire +1 more source
It is well known that the language obtained by deleting an arbitrary language from a regular language is regular. We give an upper bound for the state complexity of deleting an arbitrary language from a regular language and a matching lower bound. We show that the state complexity of deletion is n ·2 n − 1 (respectively, \((n + \frac{1}{2}) \cdot 2^n -
Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
openaire +1 more source
State Complexity of Shuffle on Trajectories
J. Autom. Lang. Comb., 2004It is easy to get an upper bound for the state complexity of shuffle on trajectories that generalizes the bound for unrestricted shuffle. We establish improved bounds for slender trajectories, that is, trajectories which have only a constant number of strings of a given length.
Michael Domaratzki, Kai Salomaa
openaire +2 more sources
STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY
International Journal of Foundations of Computer Science, 2012Finite-state complexity is a variant of algorithmic information theory obtained by replacing Turing machines with finite transducers. We consider the number of states needed for transducers used in minimal descriptions of arbitrary strings and, as our main result, show that the state-size hierarchy with respect to a standard encoding is infinite.
Cristian S. Calude +2 more
openaire +2 more sources
State Complexity of Pseudocatenation
2019The state complexity of a regular language \(L_m\) is the number m of states in a minimal deterministic finite automaton (DFA) accepting \(L_m\). The state complexity of a regularity-preserving binary operation on regular languages is defined as the maximal state complexity of the result of the operation, where the two operands range over all languages
Lila Kari, Timothy Ng 0001
openaire +1 more source
State Complexity of Projected Languages
2011This paper discusses the state complexity of projected regular languages represented by incomplete deterministic finite automata. It is shown that the known upper bound is reachable only by automata with one unobservable transition, that is, a transition labeled with a symbol removed by the projection.
Galina Jirásková, Tomás Masopust
openaire +2 more sources