UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
From MaRDI portal
Publication:3021944
DOI10.1142/S012905410200100XzbMath1066.68072OpenAlexW1988560957WikidataQ61677531 ScholiaQ61677531MaRDI QIDQ3021944
Giovanni Pighizzini, Jeffrey O. Shallit
Publication date: 22 June 2005
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s012905410200100x
Related Items (68)
Closure properties and descriptional complexity of deterministic regular expressions ⋮ Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. ⋮ Operations on Permutation Automata ⋮ The state complexity of \(L^{2}\) and \(L^k\) ⋮ Operational State Complexity of Subtree-Free Regular Tree Languages ⋮ State Complexity of Boundary of Prefix-Free Regular Languages ⋮ STATE COMPLEXITY OF CODE OPERATORS ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-STAR AND CATENATION-REVERSAL ⋮ State complexity of combined operations ⋮ Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages ⋮ Boolean language operations on nondeterministic automata with a pushdown of constant height ⋮ Lattice Point Visibility on Generalized Lines of Sight ⋮ On the minimization of XML schemas and tree automata for unranked trees ⋮ Quotient complexity of closed languages ⋮ State complexity of star of union and square of union on \textit{k} regular languages ⋮ State complexity of combined operations for suffix-free regular languages ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ Unambiguous finite automata over a unary alphabet ⋮ State complexity of union and intersection of star on \(k\) regular languages ⋮ Usefulness of information and decomposability of unary regular languages ⋮ Operational complexity in subregular classes ⋮ State Complexity of Insertion ⋮ Descriptional complexity of limited automata ⋮ Concatenation of regular languages and descriptional complexity ⋮ State complexity of combined operations with two basic operations ⋮ Nondeterministic state complexity of star-free languages ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES ⋮ NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES ⋮ Usefulness of information and unary languages ⋮ QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES ⋮ SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA ⋮ On the descriptional complexity of finite automata with modified acceptance conditions ⋮ State complexity of some operations on binary regular languages ⋮ Complementing unary nondeterministic automata ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Estimation of state complexity of combined operations ⋮ State complexity of union and intersection of square and reversal on \(k\) regular languages ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Power, positive closure, and quotients on convex languages ⋮ Decidability and Shortest Strings in Formal Languages ⋮ State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal ⋮ State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet ⋮ New methods to find patches of invisible integer lattice points ⋮ Most Complex Non-Returning Regular Languages ⋮ Square on Deterministic, Alternating, and Boolean Finite Automata ⋮ State Complexity of Combined Operations for Prefix-Free Regular Languages ⋮ Regular Expressions with Counting: Weak versus Strong Determinism ⋮ STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION ⋮ State complexity of power ⋮ Decimations of languages and state complexity ⋮ Concatenation of Regular Languages and Descriptional Complexity ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Descriptional Complexity of Bounded Regular Languages ⋮ On the Adjacency-Jacobsthal numbers ⋮ State complexity of basic operations on suffix-free regular languages ⋮ Descriptional complexity of regular languages ⋮ On Simulation Cost of Unary Limited Automata ⋮ State complexity of unambiguous operations on finite automata ⋮ Undecidability of state complexity ⋮ Commutative regular languages with product-form minimal automata ⋮ State complexity investigations on commutative languages -- the upward and downward closure, commutative aperiodic and commutative group languages ⋮ Simulating finite automata with context-free grammars. ⋮ State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages ⋮ State complexity of GF(2)-operations on unary languages
Cites Work
- Finite automata and unary languages
- The state complexities of some basic operations on regular languages
- Über eine zahlentheoretische Funktion von Jacobsthal
- On a question of regarding visibility of lattice points
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- On a Problem of Partitions
This page was built for publication: UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
