A survey on operational state complexity
From MaRDI portal
Publication:4590910
DOI10.25596/JALC-2016-251zbMATH Open1380.68253arXiv1509.03254MaRDI QIDQ4590910FDOQ4590910
Authors: Yuan Gao, Nelma Moreira, Rogério Reis, Sheng Yu 
Publication date: 20 November 2017
Full work available at URL: https://arxiv.org/abs/1509.03254
Recommendations
automata theorydescriptional complexityregular languagesstate complexityoperational state complexity
Cited In (50)
- Complexity of operation problems
- Primitivity, uniform minimality, and state complexity of Boolean operations
- Complexity of proper prefix-convex regular languages
- Combination of roots and Boolean operations: an application to state complexity
- State complexity of projection on languages recognized by permutation automata and commuting letters
- Networks with evolutionary processors and ideals and codes as filters
- State complexity of finite partial languages
- Operational union-complexity
- State complexity of permutation and related decision problems on alphabetical pattern constraints
- Title not available (Why is that?)
- State complexity of combined operations involving catenation and binary Boolean operations: beyond the Brzozowski conjectures
- Operational complexity and right linear grammars
- Descriptional complexity of iterated uniform finite-state transducers
- State complexity bounds for the commutative closure of group languages
- Descriptional complexity of semi-simple splicing systems
- Operational accepting state complexity: the unary and finite case
- Remarks on context-free grammars with subregular control languages
- On the decidability of infix inclusion problem
- State complexity of suffix distance
- New tools for state complexity
- Further Remarks on the Operational Nonterminal Complexity
- Descriptional complexity of the forever operator
- State complexity of overlap assembly
- Operational State Complexity under Parikh Equivalence
- Operational state complexity revisited: the contribution of monsters and modifiers
- On the decidability of infix inclusion problem
- Cellular automata: descriptional complexity and decidability
- Descriptional complexity of bounded regular languages
- Binary and circular automata having maximal state complexity for the set of synchronizing words
- On the accepting state complexity of operations on permutation automata
- Descriptional complexity of finite automata -- selected highlights
- On the accepting state complexity of operations on permutation automata
- State complexity of finite partial languages
- The descriptional power of queue automata of constant length
- Nondeterministic complexity in subclasses of convex languages
- Operational complexity and pumping lemmas
- State complexity of regular languages
- Title not available (Why is that?)
- Finite automata with undirected state graphs
- A Study of a Simple Class of Modifiers: Product Modifiers
- State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
- Descriptional complexity of regular languages
- Solving string constraints using SAT
- State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
- The commutative closure of shuffle languages over group languages is regular
- State complexity of pattern matching in regular languages
- Completely distinguishable automata and the set of synchronizing words
- 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
- Descriptional Complexity of Semi-Simple Splicing Systems
This page was built for publication: A survey on operational state complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4590910)
