The complexity of concatenation on deterministic and alternating finite automata

DOI10.1051/ITA/2018011MaRDI QIDQ5223613zbMATH OpenOpenAlexWikidataFDO

Authors Michal Hospodár, Galina Jirásková

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 languagesconcatenationstate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Concatenation of regular languages and descriptional complexity
• Concatenation of Regular Languages and Descriptional Complexity
• Implementation and Application of Automata
• Concatenation operations and restricted variants of two-dimensional automata
• State complexity of the concatenation of regular tree languages
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Multiple concatenation and state complexity (extended abstract)
• The complexity of languages resulting from the concatenation operation
• The Complexity of Languages Resulting from the Concatenation Operation
• The state complexity of alternating automata

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• Constructions for alternating finite automata^∗
• Descriptional Complexity of Operations on Alternating and Boolean Automata
• On equations for regular languages, finite automata, and sequential networks
• On generalized language equations
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• State complexity of some operations on binary regular languages
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages

Cited in

(11)

• Concatenation operations and restricted variants of two-dimensional automata
• A new technique for reachability of states in concatenation automata
• scientific article; zbMATH DE number 3894493 (Why is no real title available?)
• Concatenation of Regular Languages and Descriptional Complexity
• Alternation in two-way finite automata
• Operations on Boolean and Alternating Finite Automata
• Descriptional complexity of \(h\)-alternating finite automata
• The complexity of languages resulting from the concatenation operation
• The Complexity of Languages Resulting from the Concatenation Operation
• The state complexity of alternating automata
• Concatenation of regular languages and descriptional complexity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5223613)