Results 241 to 250 of about 697,927 (279)
Some of the next articles are maybe not open access.
On Approximating Non-regular Languages by Regular Languages
Fundamenta Informaticae, 2011Approximate computation is a central concept in algorithms and computation theory. Our notion of approximation is that the algorithm performs correctly on most of the inputs. We propose some finite automata models to study the question of how well a finite automaton can approximately recognize a non-regular language.
Gerry Eisman, Bala Ravikumar
openaire +1 more source
Fundamenta Informaticae, 2007
Intercodes are a generalization of comma-free codes. Using the structural properties of finite-state automata recognizing an intercode we develop a polynomial-time algorithm for determining whether or not a given regular language L is an intercode.
Han, Yo-Sub, Salomaa, Kai, Wood, Derick
openaire +3 more sources
Intercodes are a generalization of comma-free codes. Using the structural properties of finite-state automata recognizing an intercode we develop a polynomial-time algorithm for determining whether or not a given regular language L is an intercode.
Han, Yo-Sub, Salomaa, Kai, Wood, Derick
openaire +3 more sources
Fundamenta Informaticae, 2017
We investigate regular languages in the context of the forbidding-enforcing systems introduced by Ehrenfeucht and Rozenberg in the variant where one fe-system defines a single language. In general, these systems may have infinite sets of rules, allowing one to define arbitrary languages.
Genova, D., Hoogeboom, H.J.
openaire +4 more sources
We investigate regular languages in the context of the forbidding-enforcing systems introduced by Ehrenfeucht and Rozenberg in the variant where one fe-system defines a single language. In general, these systems may have infinite sets of rules, allowing one to define arbitrary languages.
Genova, D., Hoogeboom, H.J.
openaire +4 more sources
IEEE Transactions on Computers, 1974
Random occurrences of three types of errors in the input to a finite automaton are considered: an α error is a deletion of one symbol from the input string; a β error is an insertion of one extra symbol; and a δ error is a change of one symbol into another symbol.
openaire +1 more source
Random occurrences of three types of errors in the input to a finite automaton are considered: an α error is a deletion of one symbol from the input string; a β error is an insertion of one extra symbol; and a δ error is a change of one symbol into another symbol.
openaire +1 more source
International Journal of Foundations of Computer Science, 2009
In this paper we prove that it is decidable whether the set pow (L), which we get by taking all the powers of all the words in some regular language L, is regular or not. The problem was originally posed by Calbrix and Nivat in 1995. Partial solutions have been given by Cachat for unary languages and by Horváth et al. for various kinds of exponent sets
openaire +1 more source
In this paper we prove that it is decidable whether the set pow (L), which we get by taking all the powers of all the words in some regular language L, is regular or not. The problem was originally posed by Calbrix and Nivat in 1995. Partial solutions have been given by Cachat for unary languages and by Horváth et al. for various kinds of exponent sets
openaire +1 more source
On the Density of Regular Languages
Fundamenta Informaticae, 2019Let ∑ be an alphabet which has at least two symbols. The density of L ⊆ ∑* is defined as D( L) := lim n | L ∩ ∑ n|/|∑ n| ∈ [0, 1], provided that the limit exists. In 2015, R. Sin’ya has discovered an interesting relation between regular languages and their densities: If L ⊆ ∑* is a regular language, then D( L) = 0 if and only if there exists s ...
openaire +2 more sources
Acta Informatica, 2008
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Chen-Ming Fan +2 more
openaire +1 more source
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Chen-Ming Fan +2 more
openaire +1 more source
Deterministic regular languages
1992The ISO standard for Standard Generalized Markup Language (SGML) provides a syntactic meta-language for the definition of textual markup systems. In the standard the right hand sides of productions are called {\sl content models} and they are based on regular expressions. The allowable regular expressions are those that are ``unambiguous'''' as defined
Anne Brüggemann-Klein, Derick Wood
openaire +1 more source
Information Sciences, 1996
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
D. S. Malik +2 more
openaire +2 more sources
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
D. S. Malik +2 more
openaire +2 more sources
J. Comput. Syst. Sci., 1992
The paper deals with the problem of recognition of regular languages by the circuits of certain type. The theory of the syntactic monoid of a regular language is used to present various characterizations of the regular languages in the circuit complexity class \(AC^ 0\). Also an effective procedure for deciding the membership of a regular language in \(
David A. Mix Barrington +3 more
openaire +1 more source
The paper deals with the problem of recognition of regular languages by the circuits of certain type. The theory of the syntactic monoid of a regular language is used to present various characterizations of the regular languages in the circuit complexity class \(AC^ 0\). Also an effective procedure for deciding the membership of a regular language in \(
David A. Mix Barrington +3 more
openaire +1 more source