Undecidability of the State Complexity of Composed Regular Operations

DOI10.1007/978-3-642-21254-3_39zbMath1330.68179OpenAlexW13816296MaRDI QIDQ3004607

Kai Salomaa, Arto Salomaa, Sheng Yu

Publication date: 3 June 2011

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21254-3_39

zbMATH Keywords

undecidabilitystate complexityfinite deterministic automatonregularity-preserving operationscomposition of operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (8)

State Complexity of Kleene-Star Operations on Trees ⋮ Undecidability of State Complexities Using Mirror Images ⋮ State complexity of star of union and square of union on \textit{k} regular languages ⋮ State complexity of union and intersection of star on \(k\) regular languages ⋮ State complexity of the concatenation of regular tree languages ⋮ State complexity of combined operations with two basic operations ⋮ State complexity of union and intersection of square and reversal on \(k\) regular languages ⋮ Lower bounds for the size of deterministic unranked tree automata

This page was built for publication: Undecidability of the State Complexity of Composed Regular Operations