Wyniki wyszukiwania - BazTech

1

A logical approach to grammar description

Clément L., Kirman J., Salvati S.

Journal of Language Modelling

|

2015

|

Vol. 3, No. 1

87--143

EN

In the tradition of Model Theoretic Syntax, we propose a logical approach to the description of grammars. We combine in one formalism several tools that are used throughout computer science for their power of abstraction: logic and lambda calculus. We propose then a high-level formalism for describing mildly context sensitive grammars and their semantic interpretation. As we rely on the correspondence between logic and finite state automata, our method combines conciseness with effectivity. We illustrate our approach with a simple linguistic model of several interleaved linguistic phenomena involving extraction. The level of abstraction provided by logic and lambda calculus allows us not only to use this linguistic model for several languages, namely English, German, and Dutch, but also for semantic interpretation.

2

An Algorithm for BCH Codes Extended with Finite State Automata

Kelarev A.

Fundamenta Informaticae

|

2008

|

Vol. 84, nr 1

51-60

EN

This article develops a combinatorial algorithm for a class of codes extending BCH codes and constructed with finite state automata. Our algorithm computes the largest number of errors that the extended codes can correct, and finds a generator for each optimal code in this class of extensions. The question of finding codes with largest possible information rates remains open.

3

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.

4

Regular Expressions for Languages over Infinite Alphabets

Kaminski M., Tan T.

Fundamenta Informaticae

|

2006

|

Vol. 69, nr 3

301-318

EN

In this paper we introduce a notion of a regular expression over infinite alphabets and show that a language is definable by an infinite alphabet regular expression if and only if it is accepted by finite-state unification based automaton - a model of computation that is tightly related to other models of automata over infinite alphabets.

5

Correcting Spelling Errors by Modelling Their Causes

Deorowicz S., Ciura M. G.

International Journal of Applied Mathematics and Computer Science

|

2005

|

Vol. 15, no 2

275-285

EN

This paper accounts for a new technique of correcting isolated words in typed texts. A language-dependent set of string substitutions reflects the surface form of errors that result from vocabulary incompetence, misspellings, or mistypings. Candidate corrections are formed by applying the substitutions to text words absent from the computer lexicon. A minimal acyclic deterministic finite automaton storing the lexicon allows quick rejection of nonsense corrections, while costs associated with the substitutions serve to rank the remaining ones. A comparison of the correction lists generated by several spellcheckers for two corpora of English spelling errors shows that our technique suggests the right words more accurately than the others.