Operational State Complexity under Parikh Equivalence

DOI10.1007/978-3-319-09704-6_26zbMath1410.68208OpenAlexW271776540WikidataQ61677494 ScholiaQ61677494MaRDI QIDQ5496197

Giovanna J. Lavado, Shinnosuke Seki, Giovanni Pighizzini

Publication date: 7 August 2014

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2434/482852

zbMATH Keywords

context-free grammarsregular languagesstate complexitysemilinear setsParikh equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (9)

State complexity of permutation on finite languages over a binary alphabet ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ Jumping automata over Infinite words ⋮ Unnamed Item ⋮ Operational State Complexity and Decidability of Jumping Finite Automata ⋮ State complexity of deletion and bipolar deletion ⋮ Operational Accepting State Complexity: The Unary and Finite Case ⋮ The State Complexity of Permutations on Finite Languages over Binary Alphabets ⋮ Nondeterministic right one-way jumping finite automata

This page was built for publication: Operational State Complexity under Parikh Equivalence