%0 Conference Proceedings
%T State Complexity of Prefix Distance of Subregular Languages
%+ Queen's University [Kingston, Canada]
%A Rappaport, David
%A Salomaa, Kai
%A Ng, Timothy
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS)
%C Bucharest, Romania
%Y Cezar Câmpeanu
%Y Florin Manea
%Y Jeffrey Shallit
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-9777
%P 192-204
%8 2016-07-05
%D 2016
%R 10.1007/978-3-319-41114-9_15
%Z Computer Science [cs]Conference papers
%X The neighbourhood of a regular language of constant radius with respect to the prefix distance is always regular. We give upper bounds and matching lower bounds for the size of the minimal deterministic finite automaton (DFA) needed for the radius k prefix distance neighbourhood of an n state DFA that recognizes, respectively, a finite, a prefix-closed and a prefix-free language. For prefix-closed languages the lower bound automata are defined over a binary alphabet. For finite and prefix-free regular languages the lower bound constructions use an alphabet that depends on the size of the DFA and it is shown that the size of the alphabet is optimal.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01633944/document
%2 https://inria.hal.science/hal-01633944/file/416473_1_En_15_Chapter.pdf
%L hal-01633944
%U https://inria.hal.science/hal-01633944
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-LNCS-9777
%~ IFIP-WG1-2