PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 19

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  regular language
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Separating the Words of a Language by Counting Factors
Saarela Aleksi
Fundamenta Informaticae
|
2021
|
Vol. 180, nr 4
375--393
EN
For a given language L, we study the languages X such that for all distinct words u, v ∈ L, there exists a word x ∈ X that appears a different number of times as a factor in u and in v. In particular, we are interested in the following question: For which languages L does there exist a finite language X satisfying the above condition? We answer this question for all regular languages and for all sets of factors of infinite words.
2
Content available On regular languages over power sets
Fernando T.
Journal of Language Modelling
|
2016
|
Vol. 4, No. 1
29--56
EN
The power set of a finite set is used as the alphabet of a string interpreting a sentence of Monadic Second-Order Logic so that the string can be reduced (in a straightforward way) to the symbols occurring in the sentence. Simple extensions to regular expressions are described matching the succinctness of Monadic Second-Order Logic. A link to Goguen and Burstall’s notion of an institution is forged, and applied to conceptions within natural language semantics of time based on change.
3
Content available remote Ambiguity of the Multiple Interpretations on Regular Languages
Alarcón P. P., Arroyo F., Bordihn H., Mitrana V., Müller M.
Fundamenta Informaticae
|
2015
|
Vol. 138, nr 1/2
85--95
EN
A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages.
4
Content available remote Filtrations of Formal Languages by Arithmetic Progressions
Mousavi H., Shallit J.
Fundamenta Informaticae
|
2013
|
Vol. 123, nr 2
135--142
EN
A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL’s that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness.
5
Content available remote State Complexity of Combined Operations with Union, Intersection, Star and Reversal
Gao Y., Yu S
Fundamenta Informaticae
|
2012
|
Vol. 116, nr 1-4
79-92
EN
In this paper, we study the state complexities of four combined operations: [formula]. The tight bounds for all these combined operations on regular languages are obtained and proved. We show that, as usual, they are different from the mathematical compositions of the state complexities of their individual participating operations.
6
Content available remote On the Shuffle of Star-Free Languages
Castiglione G., Restivo A.
Fundamenta Informaticae
|
2012
|
Vol. 116, nr 1-4
35-44
EN
Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is starfree. Some of the special cases here approached give rise to new problems in combinatorics on words.
7
Content available remote A Characterization of Regular Languages as Equality Sets of HDT0L Sequences
Honkala J.
Fundamenta Informaticae
|
2012
|
Vol. 116, nr 1-4
123-128
EN
We characterize regular languages as the equality sets of sequences generated by compatible uniform HDT0L systems.
8
Content available remote Transition Complexity of Incomplete DFAs
Gao Y., Salomaa K., Yu S
Fundamenta Informaticae
|
2011
|
Vol. 110, nr 1-4
143-158
EN
We consider the transition complexity of regular languages based on the incomplete deterministic finite automata. We establish tight bounds for the transition complexity of Boolean operations, in the case of union the upper and lower bounds differ by a multiplicative constant two. We show that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity bounds turn out to be similar to the corresponding bounds for state complexity.
9
Content available remote Rough Approximations in Varieties of Regular Languages
Martin G., Steinby M.
Fundamenta Informaticae
|
2011
|
Vol. 112, nr 4
281-303
EN
We study approximations of regular languages bymembers of a given variety L of regular languages. These are upper or lower approximations in the sense of Pawlak’s rough set theory with respect to congruences belonging to the variety of congruences corresponding to L. In particular, we consider the closest upper and lower approximations in L. In so-called principal varieties these always exist, and we present algorithms for finding them, but for other varieties the situation is more complex. Although we consider just Eilenberg’s +-varieties, the general ideas apply also to other types of varieties of languages. Our work may also be viewed as an approach to the characterizable inference problem in which a language of a certain kind is to be inferred from a given sample.
10
Content available remote Computing Maximal Error-detecting Capabilities and Distances of Regular Languages
Konstantinidis S., Silva P.V.
Fundamenta Informaticae
|
2010
|
Vol. 101, nr 4
257-270
EN
A (combinatorial) channel consists of pairs of words representing all possible inputoutput channel situations. In a past paper, we formalized the intuitive concept of "largest amount of errors" detectable by a given language L, by defining the maximal error-detecting capabilities of L with respect to a given class of channels, and we showed how to compute all maximal error-detecting capabilities (channels) of a given regular language with respect to the class of rational channels and a class of channels involving only the substitution-error type. In this paper we resolve the problem for channels involving any combination of the basic error types: substitution, insertion, deletion. Moreover, we consider the problem of finding the inverses of these channels, in view of the fact that L is error-detecting for γif and only if it is error-detecting for the inverse of γ. We also discuss a natural method of reducing the problem of computing (inner) distances of a given regular language L to the problem of computing maximal error-detecting capabilities of L
11
Content available remote Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
Han Y-S., Salomaa K., Wood D.
Fundamenta Informaticae
|
2009
|
Vol. 90, nr 1-2
93-106
EN
We investigate the nondeterministic state complexity of basic operations for prefix-free regular languages. The nondeterministic state complexity of an operation is the number of states that are necessary and sufficient in the worst-case for a minimal nondeterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, union, intersection, Kleene star, reversal and complementation for prefix-free regular languages.
12
Content available remote Outfix-Free Regular Languages and Prime Outfix-Free Decomposition
Han Y-S., Wood D.
Fundamenta Informaticae
|
2007
|
Vol. 81, nr 4
441-457
EN
A string x is an outfix of a string y if there is a string w such that x1wx2=y and x = x1x2. A set X of strings is outfix-free if no string in X is an outfix of any other string in X. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines outfix-freeness of regular languages. Note that outfix-free regular languages are always finite. We consider two cases: 1) a language is given as a finite set of strings and 2) a language is given by a finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfix-free regular languages and design a linear-time algorithm that computes prime outfix-free decomposition for outfix-free regular languages. We also demonstrate the uniqueness of prime outfix-free decomposition.
13
Content available remote Intercode Regular Languages
Han Y-S., Salomaa K., Wood D.
Fundamenta Informaticae
|
2007
|
Vol. 76, nr 1-2
113-128
EN
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. If the answer is yes, our algorithm yields also the smallest index k such that L is a k-intercode. Furthermore, we examine the prime intercode decomposition of intercode regular languages and design an algorithm for the intercode primality test of an intercode recognized by a finite-state automaton. We also propose an algorithm that computes the prime intercode decomposition of an intercode regular language in polynomial time. Finally, we demonstrate that the prime intercode decomposition need not be unique.
14
Content available remote Undecidability in w-Regular Languages
Halava V., Harju T., Karhumäki J.
Fundamenta Informaticae
|
2006
|
Vol. 73, nr 1-2
119-125
EN
In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word a such that h(a) = g(a). In the general case this problem was shown to be undecidable by K. Ruohonen (1985). Recently, it was proved that the infinite PCP is undecidable already when the domain alphabet of the morphisms consists of at least 9 letters. Here we show that the problem is undecidable for instances where the morphisms have a domain of 6 letters, when we restrict to solutions of w-languages of the form Rw where R is a given regular language.
15
Content available remote State Complexity : Recent Results and Open Problems
Yu S
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
471-480
EN
In this paper, we summarize recent results and progress in state complexity research. We analyze why many basic state complexity problems were not solved earlier, in the sixties and seventies. We also suggest several future directions for this area of research.
16
Content available remote New Iteration Lemmata for Regular Languages
Dömösi P., Kudlek M.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
151-157
EN
Using well-known characterizations of regular languages, on the basis of known iteration lemmas, new iteration lemmas for regular languages are given.
17
Content available remote Contextual Grammars with Uniform Sets of Trajectories
Okhotin A., Salomaa K.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
341-351
EN
A uniform contextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the non-uniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.
18
Content available remote On One-Way Cellular Automata with a Fixed Number of Cells
Malcher A.
Fundamenta Informaticae
|
2003
|
Vol. 58, nr 3,4
355--368
EN
We investigate a restricted one-way cellular automaton (OCA) model where the number of cells is bounded by a constant number k, so-called kC-OCAs. In contrast to the general model, the generative capacity of the restricted model is reduced to the set of regular languages. A kC-OCA can be algorithmically converted to a deterministic finite automaton (DFA). The blow-up in the number of states is bounded by a polynomial of degree k. We can exhibit a family of unary languages which shows that this upper bound is tight in order of magnitude. We then study upper and lower bounds for the trade-off when converting DFAs to kC-OCAs. We show that there are regular languages where the use of kC-OCAs cannot reduce the number of states when compared to DFAs. We then investigate trade-offs between kC-OCAs with different numbers of cells and finally treat the problem of minimizing a given kC-OCA
19
Content available remote Decision trees for regular language word recognition
Moshkov M.
Fundamenta Informaticae
|
2000
|
Vol. 41, Nr 4
449-461
EN
In this paper the problem of recognition of words with fixed length from a regular language is considered. The word under consideration can be interpreted as a description of certain screen image in the following way: the i-th letter of the word encodes the color of the i-th screen cell. In this case a decision tree which recognizes some words may be interpreted as an algorithm for the recognition of images which are defined by considered words. The classification of all regular languages depending on the growth of minimal depth of decision trees for language word recognition with the growth of the word length is obtained. In proofs methods of test theory and rough set theory are used.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.