scientific article; zbMATH DE number 6810359
From MaRDI portal
Publication:4590910
DOI10.25596/jalc-2016-251zbMath1380.68253arXiv1509.03254MaRDI QIDQ4590910
Yuan Gao, Rogério Reis, Nelma Moreira, Sheng Yu
Publication date: 20 November 2017
Full work available at URL: https://arxiv.org/abs/1509.03254
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
automata theoryregular languagesstate complexitydescriptional complexityoperational state complexity
Related Items (42)
A Study of a Simple Class of Modifiers: Product Modifiers ⋮ Descriptional Complexity of Semi-simple Splicing Systems ⋮ State complexity of projection on languages recognized by permutation automata and commuting letters ⋮ On the decidability of infix inclusion problem ⋮ Operational complexity and pumping lemmas ⋮ Completely distinguishable automata and the set of synchronizing words ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ State complexity of pattern matching in regular languages ⋮ Unnamed Item ⋮ Further Remarks on the Operational Nonterminal Complexity ⋮ Cellular Automata: Descriptional Complexity and Decidability ⋮ Descriptional Complexity of Semi-Simple Splicing Systems ⋮ Operational state complexity revisited: the contribution of monsters and modifiers ⋮ Binary and circular automata having maximal state complexity for the set of synchronizing words ⋮ On the accepting state complexity of operations on permutation automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Descriptional Complexity of the Forever Operator ⋮ Finite automata with undirected state graphs ⋮ State complexity of finite partial languages ⋮ Operational Accepting State Complexity: The Unary and Finite Case ⋮ State Complexity of Suffix Distance ⋮ Operational complexity and right linear grammars ⋮ The descriptional power of queue automata of constant length ⋮ Descriptional complexity of iterated uniform finite-state transducers ⋮ Networks with Evolutionary Processors and Ideals and Codes as Filters ⋮ Complexity of proper prefix-convex regular languages ⋮ Unnamed Item ⋮ Descriptional Complexity of Bounded Regular Languages ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Descriptional complexity of regular languages ⋮ Primitivity, uniform minimality, and state complexity of Boolean operations ⋮ State complexity of combined operations involving catenation and binary Boolean operations: beyond the Brzozowski conjectures ⋮ 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 ⋮ State Complexity of Overlap Assembly ⋮ Combination of roots and Boolean operations: an application to state complexity ⋮ State complexity of finite partial languages ⋮ Operational union-complexity ⋮ The commutative closure of shuffle languages over group languages is regular ⋮ State complexity of permutation and related decision problems on alphabetical pattern constraints
This page was built for publication:
