The complexity of concatenation on deterministic and alternating finite automata

DOI10.1051/ita/2018011zbMath1486.68096OpenAlexW2913798541WikidataQ128539404 ScholiaQ128539404MaRDI QIDQ5223613

Galina Jirásková, Michal Hospodár

Publication date: 18 July 2019

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ita/2018011

zbMATH Keywords

finite automataregular languagesstate complexityconcatenation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Operations on Boolean and Alternating Finite Automata ⋮ Alternation in two-way finite automata

Cites Work

• On equations for regular languages, finite automata, and sequential networks
• On generalized language equations
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages
• State complexity of some operations on binary regular languages
• Descriptional Complexity of Operations on Alternating and Boolean Automata
• Constructions for alternating finite automata^∗
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of concatenation on deterministic and alternating finite automata