State complexity of unique rational operations

DOI10.1016/j.tcs.2009.02.035zbMath1168.68029OpenAlexW2084869467MaRDI QIDQ1019724

Narad Rampersad, Bala Ravikumar, Jeffrey O. Shallit, Nicolae Sântean

Publication date: 4 June 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.02.035

zbMATH Keywords

state complexityunique concatenationunique starunique union

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items

On Language Decompositions and Primality ⋮ Language Decompositions, Primality, and Trajectory-Based Operations ⋮ State complexity of unique rational operations ⋮ State complexity of unambiguous operations on finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The state complexity of \(L^{2}\) and \(L^k\)
• State complexity of unique rational operations
• A note on the space complexity of some decision problems for finite automata
• Intersection and union of regular languages and state complexity
• On finite semigroups of matrices
• The state complexities of some basic operations on regular languages
• On language equations with invertible operations
• Complexity results for two-way and multi-pebble automata and their logics
• Communication complexity method for measuring nondeterminism in finite automata
• State complexity of combined operations
• Relationships between nondeterministic and deterministic tape complexities
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Ambiguity in Graphs and Expressions
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES