Wyniki wyszukiwania - BazTech

1

Reversible Regular Languages : Logical and Algebraic Characterisations

Gastin Paul, Manuel Amaldev, Govind R.

Fundamenta Informaticae

|

2021

|

Vol. 180, nr 4

333--350

EN

We present first-order (FO) and monadic second-order (MSO) logics with predicates ‘between’ and ‘neighbour’ that characterise the class of regular languages that are closed under the reverse operation and its subclasses. The ternary between predicate bet(x, y, z) is true if the position y is strictly between the positions x and z. The binary neighbour predicate N(x, y) is true when the the positions x and y are adjacent. It is shown that the class of reversible regular languages is precisely the class definable in the logics MSO(bet) and MSO(N). Moreover the class is definable by their existential fragments EMSO(bet) and EMSO(N), yielding a normal form for MSO formulas. In the first-order case, the logic FO(bet) corresponds precisely to the class of reversible languages definable in FO(<). Every formula in FO(bet) is equivalent to one that uses at most 3 variables. However the logic FO(N) defines only a strict subset of reversible languages definable in FO(+1). A language-theoretic characterisation of the class of languages definable in FO(N), called locally-reversible threshold-testable (LRTT), is given. In the second part of the paper we show that the standard connections that exist between MSO and FO logics with order and successor predicates and varieties of finite semigroups extend to the new setting with the semigroups extended with an involution operation on its elements. The case is different for FO(N) where we show that one needs an additional equation that uses the involution operator to characterise the class. While the general problem of characterising FO(N) is open, an equational characterisation is shown for the case of neutral letter languages.

2

Unavoidable Sets, Prefix Graphs and Regularity of Circular Splicing Languages

Bonizzoni Paola, De Felice Clelia, Zaccagnino Rocco, Zizza Rosalba

Fundamenta Informaticae

|

2020

|

Vol. 171, nr 1-4

81--95

EN

Circular splicing systems are a mathematical model, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A, an initial set I of circular words, and a set R of rules. A circular splicing language is a language generated by a circular splicing system. An open problem is to characterize regular circular splicing languages and the corresponding circular splicing systems. In this framework an important role is played by unavoidable sets. These sets have been considered in several contexts. In particular, Ehrenfeucht, Haussler and Rozenberg (1983) proved the following generalization of a famous Higman’s theorem: the quasi-order induced by insertions of words from a fixed finite set is a well-quasi-order if and only if the finite set is unavoidable. In this paper we survey the known relations between unavoidable sets and regular circular languages. Motivated by these connections we give an alternative and simpler proof of the Ehrenfeucht, Haussler and Rozenberg result. Our proof is strongly based on a known characterization of unavoidable sets in terms of graphs associated with them.

3

Extracting Subregular constraints from Regular stringsets

Rogers James, Lambert Dakotah

Journal of Language Modelling

|

2019

|

Vol. 7, No. 2

143--176

EN

We introduce algorithms that, given a finite-state automaton (FSA), compute a minimal set of forbidden local factors that define a Strictly Local (SL) tight approximation of the stringset recognised by the FSA and the set of forbidden piecewise factors that define a Strictly Piecewise (SP) tight approximation of that stringset, as well as a set of co-SL factors that, together with the SL and SP factors, provide a set of purely conjunctive literal constraints defining a minimal superset of the stringset recognised by the automaton. Using these, we have built computational tools that have allowed us to reproduce, by nearly purely computational means, the work of Rogers and his co-workers (Rogers et al. 2012) in which, using a mix of computational and analytical techniques, they completely characterised, with respect to the Local and Piecewise Subregular hierarchies, the constraints on the distribution of stress in human languages that are documented in the StressTyp2 database. Our focus, in this paper, is on the algorithms and the method of their application. The phonology of stress patterns is a particularly good domain of application since, as we show here, they generally fall at the very lowest levels of complexity. We discuss these phonological results here, but do not consider their consequences in depth.

4

Word Matrix Rewriting Systems

Bisht Raj Kishor, Nishida Taishin Yasunobu, Yamamoto Kouhei

Fundamenta Informaticae

|

2019

|

Vol. 166, nr 3

199--226

EN

We introduce word matrices and word matrix rewriting systems. A word matrix over an alphabet ∑ of k letters is a k × n rectangular matrix with entries of nonnegative integers. A word matrix represents a set of words. The i-th row corresponds to the i-th letter in ∑ (thus the letters in ∑ are ordered as a1, . . . , ak). Each column vector represents a set of words which have the vector as the Parikh vector. The word matrix represents the concatenation of all sets represented by column vectors. A word matrix rewriting system consists of a set of rewriting rules which rewrite word matrices and an initial word matrix (the axiom). A word matrix rewriting system generates a set of word matrices by iterated applications of rules to the axiom and generates a language which is the union of all sets represented by the matrices. A word matrix rewriting system is a kind of (restricted) parallel rewriting system with scattered context dependency and hence can generate non-context-free languages, e.g., {anbncn | 1 ≤ n}. We define variants of word matrix rewriting systems and show an infinite hierarchy among them. Some language theoretical problems, including relations among Chomsky hierarchy, closure properties, and decision properties, are considered.

5

On the Density of Regular Languages

Koga Toshihiro

Fundamenta Informaticae

|

2019

|

Vol. 168, nr 1

45--49

EN

Let ∑ be an alphabet which has at least two symbols. The density of L ⊆ ∑* is defined as D(L) := limn |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 ∈ ∑* such that ∑*s∑* ∩ L = Ø. In this paper, we give a simple proof of this theorem, obtaining it as a simple consequence of the pumping lemma for regular languages.

6

Morphic Characterizations of Language Families Based on Local and Star Languages

Okubo F., Yokomori T.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

323--341

EN

New morphic characterizations in the form of a noted Chomsky-Schützenberger theorem are established for the classes of regular languages, of context-free languages and of languages accepted by chemical reaction automata. Our results include the following: (i) Each λ-free regular language R can be expressed as R = h(Tk ∩ FR) for some 2-star language FR, an extended 2-star language Tk and a weak coding h. (ii) Each λ-free context-free language L can be expressed as L = h(Dn ∩ FL) for some 2-local language FL and a projection h. (iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language FL and a weak coding h such that L = h(Bn ∩ FL), where Dn and Bn are a Dyck set and a partially balanced language defined over the n-letter alphabet, respectively. These characterizations improve or shed new light on the previous results.

7

k-Abelian Equivalence and Rationality

Cassaigne J., Karhumäki J., Puzynina S., Whiteland M. A.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

65--94

EN

Two words u and v are said to be k-abelian equivalent if, for each word x of length at most k, the number of occurrences of x as a factor of u is the same as for v. We study some combinatorial properties of k-abelian equivalence classes. Our starting point is a characterization of k-abelian equivalence by rewriting, so-called k-switching. Using this characterization we show that, over any fixed alphabet, the language of lexicographically least representatives of k-abelian equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is ℕ-rational. Furthermore, we show that the above sequence is asymptotically equal to a certain polynomial depending on k and the alphabet size.

8

Enforcing Regular Languages

Genova D., Hoogeboom H. J.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

131--144

EN

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. On the other hand when restricted to finite sets, one obtains a strict subclass of the regular languages, between the strictly locally testable and locally testable languages. We further investigate classes of enforcing systems that characterize the regular languages. These systems have infinite sets of enforcers, but can be defined using regular languages (finite state automata).

9

Distinguishability Operations and Closures

Câmpeanu C., Moreira N., Reis R.

Fundamenta Informaticae

|

2016

|

Vol. 148, nr 3/4

243--266

EN

Given a language L, we study the language of words D(L), that distinguish between pairs of different left quotients of L. We characterize this distinguishability operation, show that its iteration has always a fixed point, and we generalize this result to operations derived from closure operators and Boolean operators. For the case of regular languages, we give an upper bound for the state complexity of the distinguishability operation, and prove its tightness. We show that the set of minimal words that can be used to distinguish between different left quotients of a regular language L has at most n - 1 elements, where n is the state complexity of L, and we also study the properties of its iteration. We generalize the results for the languages of words that distinguish between pairs of different right quotients and two-sided quotients of a language L.

10

Two-way Automata and Regular Languages of Overlapping Tiles

Dicky A., Janin D.

Fundamenta Informaticae

|

2015

|

Vol. 141, nr 4

311--343

EN

We consider classes of languages of overlapping tiles, i.e., subsets of the McAlister monoid: the class REG of languages definable by Kleene’s regular expressions, the class MSO of languages definable by formulas of monadic second-order logic, and the class REC of languages definable by morphisms into finite monoids. By extending the semantics of finite-state two-way automata (possibly with pebbles) from languages of words to languages of tiles, we obtain a complete characterization of the classes REG and MSO. In particular, we show that adding pebbles strictly increases the expressive power of two-way automata recognizing languages of tiles, but the hierarchy induced by the number of allowed pebbles collapses to level one.

11

Optimal supervisory control of regular languages

Ray A., Fu J., Lagoa C.

Demonstratio Mathematica

|

2004

|

Vol. 37, nr 4

991--1013

EN

This paper presents an algorithm for optimal control of regular languages, realized as deterministic finite state automata (DFSA), with (possible) penalty on event disabling. A signed real measure quantifies the behavior of controlled sublanguages based on a state transition cost matrix and a characteristic vector as reported in an earlier publication. The performance index for the proposed optimal policy is obtained by combining the measure of the supervised plant language with the cost of disabled controllable event(s). Synthesis of this optimal control policy requires at most n iterations, where n is the number of states of the DFSA model generated from the unsupervised regular language. The computational complexity of the optimal control synthesis is polynomial in n. The control algorithms are illustrated with an application example of a twin-engine surveillance aircraft.