State complexity of unique rational operations

DOI10.1016/J.TCS.2009.02.035MaRDI QIDQ1019724zbMATH OpenOpenAlexFDO

Authors Narad Rampersad, B. Ravikumar, N. Sântean, Jeffrey Shallit

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)

Recommendations

• The average state complexity of rational operations on finite languages
• On the State Complexity of Combined Operations
• State complexity of combined operations
• State complexity of unambiguous operations on finite automata
• State complexity and approximation
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• State complexity of unambiguous operations on deterministic finite automata
• Undecidability of the state complexity of composed regular operations
• Operational State Complexity under Parikh Equivalence
• Estimation of state complexity of combined operations

Cites work

• scientific article; zbMATH DE number 1949643 (Why is no real title available?)
• scientific article; zbMATH DE number 2081044 (Why is no real title available?)
• scientific article; zbMATH DE number 1773072 (Why is no real title available?)
• scientific article; zbMATH DE number 2182451 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1916664 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• A note on the space complexity of some decision problems for finite automata
• Ambiguity in Graphs and Expressions
• Communication complexity method for measuring nondeterminism in finite automata
• Complexity results for two-way and multi-pebble automata and their logics
• Intersection and union of regular languages and state complexity
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On finite semigroups of matrices
• On language equations with invertible operations
• Regular expressions: new results and open problems
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Relationships between nondeterministic and deterministic tape complexities
• State complexity of combined operations
• State complexity of unique rational operations
• The state complexities of some basic operations on regular languages
• The state complexity of \(L^{2}\) and \(L^k\)
• The state complexity of two combined operations: star of catenation and star of reversal

Cited in

(7)

• scientific article; zbMATH DE number 7315090 (Why is no real title available?)
• On language decompositions and primality
• State complexity of unique rational operations
• The average state complexity of rational operations on finite languages
• Complexity of exclusive nondeterministic finite automata
• State complexity of unambiguous operations on finite automata
• Language Decompositions, Primality, and Trajectory-Based Operations

This page was built for publication: State complexity of unique rational operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1019724)