A New Technique for Reachability of States in Concatenation Automata

Abstract : We present a new technique for demonstrating the reachability of states in deterministic finite automata representing the concatenation of two languages. Such demonstrations are a necessary step in establishing the state complexity of the concatenation of two languages, and thus in establishing the state complexity of concatenation as an operation. Typically, ad-hoc induction arguments are used to show particular states are reachable in concatenation automata. We prove some results that seem to capture the essence of many of these induction arguments. Using these results, reachability proofs in concatenation automata can often be done more simply and without using induction directly.
Document type :
Conference papers
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01905633
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:25 AM
Last modification on : Friday, October 26, 2018 - 8:05:08 AM
Long-term archiving on : Sunday, January 27, 2019 - 12:38:42 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Sylvie Davies. A New Technique for Reachability of States in Concatenation Automata. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.75-87, ⟨10.1007/978-3-319-94631-3_7⟩. ⟨hal-01905633⟩

Share

Metrics

Record views

243