Journal articles: 'Chomsky hierarchy'

1

Paun, Gheorghe. "Controlled H Systems and Chomsky Hierarchy." Fundamenta Informaticae 30, no. 1 (1997): 45–57. http://dx.doi.org/10.3233/fi-1997-30104.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Jurdzinski, Tomasz, and Krzysztof Lorys. "Leftist Grammars and the Chomsky Hierarchy." Theory of Computing Systems 41, no. 2 (2007): 233–56. http://dx.doi.org/10.1007/s00224-007-2017-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Dömösi, Pál, Szilárd Fazekas, and Ito Masami. "On Chomsky Hierarchy of Palindromic Languages." Acta Cybernetica 22, no. 3 (2016): 703–13. http://dx.doi.org/10.14232/actacyb.22.3.2016.10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Berstel, Jean, Luc Boasson, and Isabelle Fagnot. "Splicing systems and the Chomsky hierarchy." Theoretical Computer Science 436 (June 2012): 2–22. http://dx.doi.org/10.1016/j.tcs.2012.03.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Fachini, Emanuela, and Angelo Monti. "CHOMSKY HIERARCHY AND SYSTOLIC Y-TREE AUTOMATA." Fundamenta Informaticae 29, no. 4 (1997): 325–39. http://dx.doi.org/10.3233/fi-1997-29402.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Jäger, Gerhard, and James Rogers. "Formal language theory: refining the Chomsky hierarchy." Philosophical Transactions of the Royal Society B: Biological Sciences 367, no. 1598 (2012): 1956–70. http://dx.doi.org/10.1098/rstb.2012.0077.

Full text

Abstract:

The first part of this article gives a brief overview of the four levels of the Chomsky hierarchy, with a special emphasis on context-free and regular languages. It then recapitulates the arguments why neither regular nor context-free grammar is sufficiently expressive to capture all phenomena in the natural language syntax. In the second part, two refinements of the Chomsky hierarchy are reviewed, which are both relevant to the extant research in cognitive science: the mildly context-sensitive languages (which are located between context-free and context-sensitive languages), and the sub-regular hierarchy (which distinguishes several levels of complexity within the class of regular languages).

APA, Harvard, Vancouver, ISO, and other styles

7

Sureshkumar, Williams, and Raghavan Rama. "Chomsky Hierarchy Control on Isotonic Array P Systems." International Journal of Pattern Recognition and Artificial Intelligence 30, no. 02 (2016): 1650004. http://dx.doi.org/10.1142/s021800141650004x.

Full text

Abstract:

In this paper, we propose a new regulated evolution in P systems with isotonic arrays and isotonic array rules. The regulated language will be a language of Chomsky hierarchy. This model generates interesting pictures for a given regulated language. The generative capacity is explored.

APA, Harvard, Vancouver, ISO, and other styles

8

Icard, Thomas F. "Calibrating generative models: The probabilistic Chomsky–Schützenberger hierarchy." Journal of Mathematical Psychology 95 (April 2020): 102308. http://dx.doi.org/10.1016/j.jmp.2019.102308.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

NIVAT, M., A. SAOUDI, and V. R. DARE. "PARALLEL GENERATION OF FINITE IMAGES." International Journal of Pattern Recognition and Artificial Intelligence 03, no. 03n04 (1989): 279–94. http://dx.doi.org/10.1142/s0218001489000243.

Full text

Abstract:

We define a syntactic model for generating sets of images, where an image can be viewed as an array over finite alphabet. This model is called image grammar. Image grammar can be considered as a generalization of classical Chomsky grammar. Then we study some combinatorial and language theoretical properties such as reduction, pumping lemmas, complexity measure, we give a strict infinite hierarchy. We also characterize these families in terms of deterministic substitutions and Chomsky languages.

APA, Harvard, Vancouver, ISO, and other styles

10

Senthil Kumar, K., and D. Malathi. "Context Free Grammar Identification from Positive Samples." International Journal of Engineering & Technology 7, no. 3.12 (2018): 1096. http://dx.doi.org/10.14419/ijet.v7i3.12.17768.

Full text

Abstract:

In grammatical inference one aims to find underlying grammar or automaton which explains the target language in some way. Context free grammar which represents type 2 grammar in Chomsky hierarchy has many applications in Formal Language Theory, pattern recognition, Speech recognition, Machine learning , Compiler design and Genetic engineering etc. Identification of unknown Context Free grammar of the target language from positive examples is an extensive area in Grammatical Inference/ Grammar induction. In this paper we propose a novel method which finds the equivalent Chomsky Normal form.

APA, Harvard, Vancouver, ISO, and other styles

11

BREVEGLIERI, LUCA, ALESSANDRA CHERUBINI, CLAUDIO CITRINI, and STEFANO CRESPI REGHIZZI. "MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS." International Journal of Foundations of Computer Science 07, no. 03 (1996): 253–91. http://dx.doi.org/10.1142/s0129054196000191.

Full text

Abstract:

A new class of languages, called multi-push-down (mpd), that generalize the classical context-free (cf, or Chomsky type 2) ones is introduced. These languages preserve some important properties of cf languages: a generalization of the Chomsky-Schützenberger homomorphic characterization theorem, the Parikh theorem and a “pumping lemma” are proved. Multi-push-down languages are an AFL. Their recognizers are automata equipped with a multi-push-down tape. Multi-push-down languages form a hierarchy based on the number of push-down tapes.

APA, Harvard, Vancouver, ISO, and other styles

12

Okubo, Fumiya, and Takashi Yokomori. "Finite Automata with Multiset Memory: A New Characterization of Chomsky Hierarchy." Fundamenta Informaticae 138, no. 1-2 (2015): 31–44. http://dx.doi.org/10.3233/fi-2015-1196.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Fujioka, Kaoru. "Morphic characterizations of languages in Chomsky hierarchy with insertion and locality." Information and Computation 209, no. 3 (2011): 397–408. http://dx.doi.org/10.1016/j.ic.2010.11.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

PĂUN, GHEORGHE, MARIO J. PÉREZ-JIMÉNEZ, and TAKASHI YOKOMORI. "REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS." International Journal of Foundations of Computer Science 19, no. 04 (2008): 859–71. http://dx.doi.org/10.1142/s0129054108006005.

Full text

Abstract:

Insertion-deletion operations are much investigated in linguistics and in DNA computing and several characterizations of Turing computability and characterizations or representations of languages in Chomsky hierarchy were obtained in this framework. In this note we contribute to this research direction with a new characterization of this type, as well as with representations of regular and context-free languages, mainly starting from context-free insertion systems of as small as possible complexity. For instance, each recursively enumerable language L can be represented in a way similar to the celebrated Chomsky-Schützenberger representation of context-free languages, i.e., in the form L = h(L(γ) ∩ D), where γ is an insertion system of weight (3, 0) (at most three symbols are inserted in a context of length zero), h is a projection, and D is a Dyck language. A similar representation can be obtained for regular languages, involving insertion systems of weight (2,0) and star languages, as well as for context-free languages – this time using insertion systems of weight (3, 0) and star languages.

APA, Harvard, Vancouver, ISO, and other styles

15

Pater, Joe. "Phonological typology in Optimality Theory and Formal Language Theory: goals and future directions." Phonology 36, no. 2 (2019): 351–53. http://dx.doi.org/10.1017/s0952675719000162.

Full text

Abstract:

Much recent work has studied phonological typology in terms of Formal Language Theory (e.g. the Chomsky hierarchy). This paper considers whether Optimality Theory grammars might be constrained to generate only regular languages, and also whether the tools of formal language theory might be used for constructing phonological theories similar to those within Optimality Theory. It offers reasons to be optimistic about the first possibility, and sceptical about the second.

APA, Harvard, Vancouver, ISO, and other styles

16

Sima, Jiri. "The Computational Power of Neural Networks and Representations of Numbers in Non-Integer Bases." MENDEL 23, no. 1 (2017): 103–10. http://dx.doi.org/10.13164/mendel.2017.1.103.

Full text

Abstract:

We briefly survey the basic concepts and results concerning the computational power of neural net-orks which basically depends on the information content of eight parameters. In particular, recurrent neural networks with integer, rational, and arbitrary real weights are classi ed within the Chomsky and finer complexity hierarchies. Then we re ne the analysis between integer and rational weights by investigating an intermediate model of integer-weight neural networks with an extra analog rational-weight neuron (1ANN). We show a representation theorem which characterizes the classification problems solvable by 1ANNs, by using so-called cut languages. Our analysis reveals an interesting link to an active research field on non-standard positional numeral systems with non-integer bases. Within this framework, we introduce a new concept of quasi-periodic numbers which is used to classify the computational power of 1ANNs within the Chomsky hierarchy.

APA, Harvard, Vancouver, ISO, and other styles

17

DASSOW, JÜRGEN, and MARKUS HOLZER. "LANGUAGE FAMILIES DEFINED BY A CILIATE BIO-OPERATION: HIERARCHIES AND DECISION PROBLEMS." International Journal of Foundations of Computer Science 16, no. 04 (2005): 645–62. http://dx.doi.org/10.1142/s0129054105003212.

Full text

Abstract:

We formalize the hairpin inverted repeat excision, which is known in ciliate genetics as an operation on words and languages by defining [Formula: see text] as the set of all words xαyRαRz where w = xαyαRz and the pointer α is in P. We extend this concept to language families which results in families [Formula: see text]. For [Formula: see text] and [Formula: see text] be the families of finite, regular, context-free, context-sensitive or recursively enumerable language, respectively, we determine the hierarchy of the families [Formula: see text] and compare these families with those of the Chomsky hierarchy. Furthermore, we present the status of decidability of the membership problem, emptiness problem and finiteness problem for the families [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

18

Sburlan, Dragoş. "Computing by Folding." International Journal of Computers Communications & Control 6, no. 4 (2011): 739. http://dx.doi.org/10.15837/ijccc.2011.4.2106.

Full text

Abstract:

The present paper introduces a new computing paradigm based on the idea of string folding. Comparisons between the computational power of the proposed model with the classical families of languages from the Chomsky hierarchy are studied. Some preliminary results are reported and some conjectures are discussed. In this respect, the proposed model is promising not only because of the expected theoretical results, but also because of the possible indirect applications in various fields (as for instance, mathematical linguistics, DNA computing, computing using light, and so on).

APA, Harvard, Vancouver, ISO, and other styles

19

Butler, Jonny. "The Structure of Temporality and Modality." Linguistic Variation Yearbook 2006 6 (December 31, 2006): 161–201. http://dx.doi.org/10.1075/livy.6.08but.

Full text

Abstract:

This paper offers a view of clause structure based on semantic interpretability, focusing on the structure and interpretation of temporal (tense, aspect) and modal elements. It proposes that modality has a unitary lexical semantics along the lines of Krater (1977 et seq), with different interpretations of modals deriving from the interaction of that semantics with the interpretation of the temporal elements in the structural context the modals are found. Different positions for modal interpretation are proposed, corresponding the the edges of phases (Chomsky 2001). Evidence for this view is put forward from various languages. The clause structure so derived is akin to the universal clausal hierarchy proposed by Cinque (1999), lending support to the notion that something like this hierarchy does indeed hold in natural language, though the justification for it is very different.

APA, Harvard, Vancouver, ISO, and other styles

20

Abdul Rahman, Aqilahfarhana, Wan Heng Fong, Nor Haniza Sarmin, Sherzod Turaev, and Nurul Liyana Mohamad Zulkufli. "Static Watson-Crick regular grammar." Malaysian Journal of Fundamental and Applied Sciences 14 (October 25, 2018): 457–62. http://dx.doi.org/10.11113/mjfas.v14n0.1282.

Full text

Abstract:

DNA computing, or more generally, molecular computing, is a recent development at the interface of computer science and molecular biology. In DNA computing, many computational models have been proposed in the framework of formal language theory and automata such as Watson-Crick grammars and sticker systems. A Watson-Crick grammar is a grammar model that generates double stranded strings, whereas a sticker system is a DNA computing model of the ligation and annealing operations over DNA strands using the Watson-Crick complementarity to form a complete double stranded DNA sequence. Most of the proposed DNA computing models make use of this concept, including the Watson-Crick grammars and sticker systems. Watson-Crick grammars and their variants can be explored using formal language theory which allows the development of new concepts of Watson-Crick grammars. In this research, a new variant of Watson-Crick grammar called a static Watson-Crick regular grammar is introduced as an analytical counterpart of sticker systems. The computation of a sticker system starts from a given set of incomplete double stranded sequence to form a complete double stranded sequence. Here, a static Watson-Crick regular grammar differs from a dynamic Watson-Crick regular grammar in generating double stranded strings: the latter grammar produces each strand string “independently” and only check for the Watson-Crick complementarity of a generated complete double stranded string at the end, while the former grammar generates both strand strings “dependently”, i.e., checking for the Watson-Crick complementarity for each complete substring. In this paper, computational properties of static Watson-Crick regular grammars are investigated to correlate with the Chomsky hierarchy and hierarchy of the families of dynamic Watson-Crick regular languages. The relationship between families of languages generated by static Watson-Crick regular grammars with several variants of sticker systems, Watson-Crick regular grammars and Chomsky grammars are presented by showing the hierarchy.

APA, Harvard, Vancouver, ISO, and other styles

21

LÁZÁR, KATALIN ANNA, ERZSÉBET CSUHAJ-VARJÚ, ANDRÁS LŐRINCZ, and GYÖRGY VASZIL. "DYNAMICALLY FORMED CLUSTERS OF AGENTS IN ECO-GRAMMAR SYSTEMS." International Journal of Foundations of Computer Science 20, no. 02 (2009): 293–311. http://dx.doi.org/10.1142/s0129054109006565.

Full text

Abstract:

In this paper we extend the conditions of dynamic team constitution in simple eco–grammar systems, motivated by the bottom–up–clustering algorithm. The relationships of simple eco–grammar systems formed according to the newly introduced conditions to each other as well as to certain language classes of the Chomsky hierarchy and L systems are established. We prove that any recursively enumerable language can be obtained as the intersection of a regular language and the language of simple eco–grammar systems where the active teams are organized according to different conditions of team constitution. We also propose some further research directions.

APA, Harvard, Vancouver, ISO, and other styles

22

ATANASIU, RADU-FLORIAN. "PARIKH MATRIX MAPPING AND LANGUAGES." International Journal of Foundations of Computer Science 21, no. 06 (2010): 993–1004. http://dx.doi.org/10.1142/s0129054110007684.

Full text

Abstract:

Restricting the Parikh Matrix mapping to a language rather than to an alphabet rises a set of problems that seem interesting to us. Moreover, amiability (or M -equivalence as it is named by other authors) is exploited in order to characterise certain types of languages. The paper also proposes a series of results establishing relations between classes of languages defined by Parikh matrix mappings and the Chomsky hierarchy. Finally, a result related to word composition concludes the paper, showing that for every two arbitrary words there exist two other words such that their composition (two by two) is amiable.

APA, Harvard, Vancouver, ISO, and other styles

23

BORDIHN, HENNING, MARKUS HOLZER, and MARTIN KUTRIB. "HYBRID EXTENDED FINITE AUTOMATA." International Journal of Foundations of Computer Science 18, no. 04 (2007): 745–60. http://dx.doi.org/10.1142/s0129054107004954.

Full text

Abstract:

Extended finite automata are finite state automata equipped with the additional ability to apply an operation on the currently remaining input word, depending on the current state. Hybrid extended finite automata can choose from a finite set of such operations. In this paper, five word operations are taken into consideration which always yield letter-equivalent results, namely reversal and shift operations. The computational power of those machines is investigated, locating the corresponding families of languages in the Chomsky hierarchy. Furthermore, different types of hybrid extended finite automata, defined by the set of operations they are allowed to apply, are compared with each other, demonstrating that there exist dependencies and independencies between the input manipulating operations.

APA, Harvard, Vancouver, ISO, and other styles

24

Öttl, Birgit, Gerhard Jäger, and Barbara Kaup. "Does Formal Complexity Reflect Cognitive Complexity? Investigating Aspects of the Chomsky Hierarchy in an Artificial Language Learning Study." PLOS ONE 10, no. 4 (2015): e0123059. http://dx.doi.org/10.1371/journal.pone.0123059.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

TIAN, Liqin, Shangmin LUAN, and Zilin GENG. "An approach to distinguishing the levels of free-labeled $L$-type Petri net languages in the Chomsky hierarchy." SCIENTIA SINICA Informationis 47, no. 6 (2017): 696. http://dx.doi.org/10.1360/n112016-00056.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Chigahara, Hiroyuki, Szilárd Zsolt Fazekas, and Akihiro Yamamura. "One-Way Jumping Finite Automata." International Journal of Foundations of Computer Science 27, no. 03 (2016): 391–405. http://dx.doi.org/10.1142/s0129054116400165.

Full text

Abstract:

We propose the one-way jumping finite automaton model, restricting the jumping relation of the recently introduced jumping finite automaton so that the machine can only jump over symbols it cannot process in its current state. The reading head of a one-way jumping finite automaton moves deterministically in one direction within the input word, whereas movement of the reading head of jumping finite automaton is non-deterministic. The class of languages accepted by one-way jumping finite automata is different from that of jumping finite automata, in particular, it includes all regular languages, as opposed to the latter. We study one-way jumping finite automata and obtain closure properties, a pumping lemma, and separation results with respect to the classical language classes of the Chomsky hierarchy.

APA, Harvard, Vancouver, ISO, and other styles

27

Fukui, Naoki. "A Note on Weak vs. Strong Generation in Human Language." Studies in Chinese Linguistics 36, no. 2 (2015): 59–68. http://dx.doi.org/10.1515/scl-2015-0004.

Full text

Abstract:

Abstract This paper argues that various important results of formal language theory (e.g., the so-called Chomsky Hierarchy) may in fact be illusory as far as the human language faculty is concerned, as has been repeatedly emphasized by Chomsky himself. The paper takes up nested dependencies and cross-serial dependencies, the two important dependencies that typically show up in the discussion of the central classes of grammars and languages, and specifically shows that the fact that nested dependencies abound in human language while cross-serial dependencies are rather limited in human language can be naturally explained if we shift our attention from dependencies defined on terminal strings to abstract structures behind them. The paper then shows that nested dependencies are readily obtained by Merge, applying phase-by-phase, whereas cross-serial dependencies are available only as a result of copying Merge, which requires a constituency of the relevant strings. These results strongly suggest that dependencies are possible in human language only to the extent that they are the results from the structures that can be generated by Merge, leading to the conclusion that it is Merge-generability that determines various dependencies in human language, and that dependencies defined on the terminal strings are indeed illusory. A possible brain science experiment to demonstrate this point is also suggested.

APA, Harvard, Vancouver, ISO, and other styles

28

Mahalingam, Kalpana, Ujjwal Kumar Mishra, and Rama Raghavan. "Watson–Crick Jumping Finite Automata." International Journal of Foundations of Computer Science 31, no. 07 (2020): 891–913. http://dx.doi.org/10.1142/s0129054120500331.

Full text

Abstract:

Watson–Crick jumping finite automata work on tapes which are double stranded sequences of symbols similar to that of Watson–Crick automata. The double stranded sequence is scanned in a discontinuous manner. That is, after reading a double stranded string, the automata can jump over some subsequence and continue scanning depending on the rule. Some variants of such automata are 1-limited, No state, All final and Simple Watson–Crick jumping finite automata. The comparison of the languages accepted by these variants with the language classes in Chomsky hierarchy has been carried out. We investigate some closure properties. We also try to place the duplication closure of a word in Watson–Crick jumping finite automata family. We have discussed the closure property of Watson–Crick jumping finite automata family under duplication operations.

APA, Harvard, Vancouver, ISO, and other styles

29

YAMAMOTO, YASUNORI, KENICHI MORITA, and KAZUHIRO SUGATA. "CONTEXT-SENSITIVITY OF TWO-DIMENSIONAL REGULAR ARRAY GRAMMARS." International Journal of Pattern Recognition and Artificial Intelligence 03, no. 03n04 (1989): 295–319. http://dx.doi.org/10.1142/s0218001489000255.

Full text

Abstract:

Regular array grammars (RAGs) are the lowest subclass in the Chomsky-like hierarchy of isometric array grammars. The left-hand side of each rewriting rule of RAGs has one nonterminal symbol and at most one "#" (a blank symbol). Therefore, the rewriting rules cannot sense contexts of non-# symbols. However, they can sense # as a kind of context. In this paper, we investigate this #-sensing ability. and study the language generating power of RAGs. Making good use of this ability, We show a method for RAGs to sense the contexts of local shapes of a host array in a derivation. Using this method, we give RAGs which generate the sets of all solid upright rectangles and all solid squares. On the other hand. it is proved that there is no context-free array grammar (and thus no RAG) which generates the set of all hollow upright rectangles.

APA, Harvard, Vancouver, ISO, and other styles

30

Holzer, Markus, Bianca Truthe, and Ahmad Firdaus Yosman. "On bonded sequential and parallel insertion systems." RAIRO - Theoretical Informatics and Applications 52, no. 2-3-4 (2018): 127–51. http://dx.doi.org/10.1051/ita/2018010.

Full text

Abstract:

We introduce a new variant of insertion systems, namely bonded insertion systems. In such systems, words are not only formed by usual letters but also by bonds between letters. Words which can be inserted, have “free” bonds at their ends which control at which positions in a word they can be inserted (namely only there, where the bonds “fit”). Two kinds of bonded insertion systems are defined in this paper: so-called bonded sequential insertion systems and bonded parallel insertion systems. In a sequential system, there is only one word inserted at a time. In a parallel system, there is a word inserted at every possible position in parallel in one time step. We investigate the generative capacity of those two kinds and relate the families of generated languages to some families of the Chomsky hierarchy and to families of languages generated by Lindenmayer systems. Additionally, we investigate some closure properties.

APA, Harvard, Vancouver, ISO, and other styles

31

Mahalingam, Kalpana, Prithwineel Paul, and Erkki Mäkinen. "On Derivation Languages of a Class of Splicing Systems." Acta Cybernetica 23, no. 4 (2018): 981–93. http://dx.doi.org/10.14232/actacyb.23.4.2018.1.

Full text

Abstract:

Derivation languages are language theoretical tools that describe halting derivation processes of a generating device. We consider two types of derivation languages, namely Szilard and control languages for splicing systems where iterated splicing is done in non-uniform way defined by Mitrana, Petre and Rogojin in 2010. The families of Szilard (rules and labels are mapped in a one to one manner) and control (more than one rule can share the same label) languages generated by splicing systems of this type are then compared with the family of languages in the Chomsky hierarchy. We show that context-free languages can be generated as Szilard and control languages and any non-empty context-free language is a morphic image of the Szilard language of this type of system with finite set of rules and axioms. Moreover, we show that these systems with finite set of axioms and regular set of rules are capable of generating any recursively enumerable language as a control language.

APA, Harvard, Vancouver, ISO, and other styles

32

Hermiller, Susan, and Zoran Šunić. "No positive cone in a free product is regular." International Journal of Algebra and Computation 27, no. 08 (2017): 1113–20. http://dx.doi.org/10.1142/s0218196717500527.

Full text

Abstract:

We show that there exists no left order on the free product of two nontrivial, finitely generated, left-orderable groups such that the corresponding positive cone is represented by a regular language. Since there are orders on free groups of rank at least two with positive cone languages that are context-free (in fact, 1-counter languages), our result provides a bound on the language complexity of positive cones in free products that is the best possible within the Chomsky hierarchy. It also provides a strengthening of a result by Cristóbal Rivas which states that the positive cone in a free product of nontrivial, finitely generated, left-orderable groups cannot be finitely generated as a semigroup. As another illustration of our method, we show that the language of all geodesics (with respect to the natural generating set) that represent positive elements in a graph product of groups defined by a graph of diameter at least 3 cannot be regular.

APA, Harvard, Vancouver, ISO, and other styles

33

Rohrmeier, Martin, Willem Zuidema, Geraint A. Wiggins, and Constance Scharff. "Principles of structure building in music, language and animal song." Philosophical Transactions of the Royal Society B: Biological Sciences 370, no. 1664 (2015): 20140097. http://dx.doi.org/10.1098/rstb.2014.0097.

Full text

Abstract:

Human language, music and a variety of animal vocalizations constitute ways of sonic communication that exhibit remarkable structural complexity. While the complexities of language and possible parallels in animal communication have been discussed intensively, reflections on the complexity of music and animal song, and their comparisons, are underrepresented. In some ways, music and animal songs are more comparable to each other than to language as propositional semantics cannot be used as indicator of communicative success or wellformedness, and notions of grammaticality are less easily defined. This review brings together accounts of the principles of structure building in music and animal song. It relates them to corresponding models in formal language theory, the extended Chomsky hierarchy (CH), and their probabilistic counterparts. We further discuss common misunderstandings and shortcomings concerning the CH and suggest ways to move beyond. We discuss language, music and animal song in the context of their function and motivation and further integrate problems and issues that are less commonly addressed in the context of language, including continuous event spaces, features of sound and timbre, representation of temporality and interactions of multiple parallel feature streams. We discuss these aspects in the light of recent theoretical, cognitive, neuroscientific and modelling research in the domains of music, language and animal song.

APA, Harvard, Vancouver, ISO, and other styles

34

Wang, Aiqing. "Wh-P and the Intervention Effect of negation." International Journal of Language and Literary Studies 3, no. 1 (2021): 12–36. http://dx.doi.org/10.36892/ijlls.v3i1.477.

Full text

Abstract:

Following the Government and Binding theory mainly developed by Chomsky (1981, 1982, 1986), I explore wh-P and the Intervention Effect of negation in Late Archaic Chinese (LAC). I propose that the inverted order of wh-P in LAC is generated via PP inversion followed by the separate preposing of wh and P. The wh-complement raises to [Spec, PP] and further moves to the specifier position of a functional projection. If the wh-PP is base-generated preverbally, the preposition moves to the head position of the functional projection directly; if the wh-PP is base-generated postverbally, the preposition must first incorporate to a V0 and then move to the head position of the functional projection through excorporation. In terms of the Intervention Effect, wh-arguments and adverbials that usually move to the Low focus position below negation are subject to a blocking effect caused by negation, so these wh-phrases have to land in the High focus position above negation which is expected to accommodate ‘high’ adverbials exclusively. I argue that the Intervention Effect in LAC is a consequence of Q-binding as feature movement of [wh], interacting with fronting into the hierarchy of clause-internal positions driven by [Focus] feature.

APA, Harvard, Vancouver, ISO, and other styles

35

Păun, Gheorghe, and Mario J. Pérez-Jiménez. "Solving Problems in a DistributedWay in Membrane Computing: dP Systems." International Journal of Computers Communications & Control 5, no. 2 (2010): 238. http://dx.doi.org/10.15837/ijccc.2010.2.2478.

Full text

Abstract:

Although P systems are distributed parallel computing devices, no explicit way of handling the input in a distributed way in this framework was considered so far. This note proposes a distributed architecture (based on cell-like P systems, with their skin membranes communicating through channels as in tissue-like P systems, according to specified rules of the antiport type), where parts of a problem can be introduced as inputs in various components and then processed in parallel. The respective devices are called dP systems, with the case of accepting strings called dP automata. The communication complexity can be evaluated in various ways: statically (counting the communication rules in a dP system which solves a given problem), or dynamically (counting the number of communication steps, of communication rules used in a computation, or the number of objects communicated). For each measure, two notions of “parallelizability" can be introduced. Besides (informal) definitions, some illustrations of these idea are provided for dP automata: each regular language is “weakly parallelizable" (i.e., it can be recognized in this framework, using a constant number of communication steps), and there are languages of various types with respect to Chomsky hierarchy which are “efficiently parallelizable" (they are parallelizable and, moreover, are accepted in a faster way by a dP automaton than by a single P automaton). Several suggestions for further research are made.

APA, Harvard, Vancouver, ISO, and other styles

36

Fong, Wan Heng, Aqilahfarhana Abdul Rahman, Nor Haniza Sarmin, and Sherzod Turaev. "Static Watson-Crick Context-Free Grammars." International Journal of Online and Biomedical Engineering (iJOE) 15, no. 10 (2019): 65. http://dx.doi.org/10.3991/ijoe.v15i10.10878.

Full text

Abstract:

Sticker systems and Watson-Crick automata are two modellings of DNA molecules in DNA computing. A sticker system is a computational model which is coded with single and double-stranded DNA molecules; while Watson-Crick automata is the automata counterpart of sticker system which represents the biological properties of DNA. Both of these models use the feature of Watson-Crick complementarity in DNA computing. Previously, the grammar counterpart of the Watson-Crick automata have been introduced, known as Watson-Crick grammars which are classified into three classes: Watson-Crick regular grammars, Watson-Crick linear grammars and Watson-Crick context-free grammars. In this research, a new variant of Watson-Crick grammar called a static Watson-Crick context-free grammar, which is a grammar counterpart of sticker systems that generates the double-stranded strings and uses rule as in context-free grammar, is introduced. The static Watson-Crick context-free grammar differs from a dynamic Watson-Crick context-free grammar in generating double-stranded strings, as well as for regular and linear grammars. The main result of the paper is to determine the generative powers of static Watson-Crick context-free grammars. Besides, the relationship of the families of languages generated by Chomsky grammars, sticker systems and Watson-Crick grammars are presented in terms of their hierarchy.

APA, Harvard, Vancouver, ISO, and other styles

37

Khulud, Al Qahtani, and Al Zahrani Mohammad. "Obligatory Movement Operations for Verbal Roots in Najdi Arabic." Advances in Language and Literary Studies 11, no. 1 (2020): 27. http://dx.doi.org/10.7575/aiac.alls.v.11n.1p.27.

Full text

Abstract:

This paper focuses on the obligatory movement operations that Najdi Arabic (NA) verb forms must undergo to satisfy the morphosyntactic requirements within the minimalist program (MP). Recall that the practice of the MP syntactic theory, including its further advancements, proposed by Chomsky (1995, 2000, 2001) springs from the fact that the grammar of a language starts basically from the lexicon from which suitable words are selected to form clauses. The selected words undergo some syntactic operations such as Merge, by which larger constituents are formed, and Move, by which the formed constituents move to higher positions in the hierarchy to fulfil some specific syntactic purposes. When the elements have undergone the operations of Merge and Move they are spelled out into phonetic forms (PF) and logical forms (LF). In light of this, we argue that NA verbs start out as roots in the head of VP before merging with the vocalic affixes in the head of Tax-AspP to satisfy the subjectverb agreement requirements and mark the aspect features. Perfective verb forms must then continue to move to T to merge with the past tense abstract features while imperfective forms stay in Tax-AspP. The thematic subject is generated in Spec,VP; it may stay there to derive the VSO order, or move higher to derive the SVO order. The findings show that obligatory movements indicate interactions between the functional categories of TP, Tax-AspP and VP: NA verbal roots obligatorily move to Tax-Asp to derive (im)perfective forms; perfectives obligatorily move to T.

APA, Harvard, Vancouver, ISO, and other styles

38

Petersson, Karl Magnus, and Peter Hagoort. "The neurobiology of syntax: beyond string sets." Philosophical Transactions of the Royal Society B: Biological Sciences 367, no. 1598 (2012): 1971–83. http://dx.doi.org/10.1098/rstb.2012.0101.

Full text

Abstract:

The human capacity to acquire language is an outstanding scientific challenge to understand. Somehow our language capacities arise from the way the human brain processes, develops and learns in interaction with its environment. To set the stage, we begin with a summary of what is known about the neural organization of language and what our artificial grammar learning (AGL) studies have revealed. We then review the Chomsky hierarchy in the context of the theory of computation and formal learning theory. Finally, we outline a neurobiological model of language acquisition and processing based on an adaptive, recurrent, spiking network architecture. This architecture implements an asynchronous, event-driven, parallel system for recursive processing. We conclude that the brain represents grammars (or more precisely, the parser/generator) in its connectivity, and its ability for syntax is based on neurobiological infrastructure for structured sequence processing. The acquisition of this ability is accounted for in an adaptive dynamical systems framework. Artificial language learning (ALL) paradigms might be used to study the acquisition process within such a framework, as well as the processing properties of the underlying neurobiological infrastructure. However, it is necessary to combine and constrain the interpretation of ALL results by theoretical models and empirical studies on natural language processing. Given that the faculty of language is captured by classical computational models to a significant extent, and that these can be embedded in dynamic network architectures, there is hope that significant progress can be made in understanding the neurobiology of the language faculty.

APA, Harvard, Vancouver, ISO, and other styles

39

KISHKAN, VLADIMIR, and KONSTANTIN SAFONOV. "DEADLOCK ALGORITHM FOR ADVANCED SYNTACTICAL ANALYSIS AND ITS APPLICATION TO PROGRAMMING LANGUAGES FOR QUANTUM COMPUTERS." Computational nanotechnology 7, no. 2 (2020): 42–48. http://dx.doi.org/10.33693/2313-223x-2020-7-2-42-48.

Full text

Abstract:

When developing promising programming languages designed to support the work of supercomputers, including quantum ones, there is a need for research related to testing the developed language under conditions when parsers do not yet exist for it. In particular, in the process of developing a programming language for a quantum computer, it becomes necessary to parse a certain program written in a new programming language, which, like all programming languages, belongs to the class of context-free languages (cf-languages). The problem of syntactical analysis of the monomials of cf-languages was posed in the 50-60s of the last century, however, there are some discrepancies in its formulation, and therefore there is a need to clarify the formulation of this problem. In this regard, we will call the expanded problem of parsing the problem of developing a stupid (non-stop, irrevocable) algorithm that allows establishing whether a given monomial can be deduced using a system of products that form a cf-language grammar, and also find all the conclusions of this monomial at once if the latter exists. The description of the monomial inference is understood as follows: it is necessary to determine for which products from the grammar of the cf-language, how many times and in what order they are used to derive this monomial, which is equivalent to constructing all the output trees. The article has developed a deadlockless algorithm for solving the extended problem of parsing, based on the method of hierarchy of marked brackets. The marked brackets order shows what products they are assigned to, and allows you to trace the order of its use. The algorithm uses the method of successive approximations to solve the Chomsky-Schützenberger system of equations associated with the cf-language grammar. The developed algorithm has a simple software implementation; an assessment of the complexity of the algorithm is also given.

APA, Harvard, Vancouver, ISO, and other styles

40

RODARO, EMANUELE, and PEDRO V. SILVA. "ON PERIODIC POINTS OF FREE INVERSE MONOID HOMOMORPHISMS." International Journal of Algebra and Computation 23, no. 08 (2013): 1789–803. http://dx.doi.org/10.1142/s0218196713500446.

Full text

Abstract:

It is proved that the periodic point submonoid of a free inverse monoid endomorphism is always finitely generated. Using Chomsky's hierarchy of languages, we prove that the fixed point submonoid of an endomorphism of a free inverse monoid can be represented by a context-sensitive language but, in general, it cannot be represented by a context-free language.

APA, Harvard, Vancouver, ISO, and other styles

41

Rita, Karla Holanda, José Ferrari-Neto, and Barbosa. "Anaphoric Processing of the Null Pronoun in Monolingual Speakers of Brazilian Portuguese: An Online Study." East European Journal of Psycholinguistics 6, no. 2 (2019): 68–79. http://dx.doi.org/10.29038/eejpl.2019.6.2.cas.

Full text

Abstract:

The aim of this paper was to investigate anaphoric processing of the null pronoun in Brazilian Portuguese and determine whether the perception of morphological gender features has a disambiguating effect during the process of reading. This feature enables the anaphoric null pronoun to be interpreted as referring to either the subject or object. We assume the proposal put forth by Carminati (2005) regarding the resolution of the null subject pronoun, which is based on the investigation of the processing of full and null pronouns in Italian. The sample of the present study was composed of 32 speakers of university-level Brazilian Portuguese. The stimuli were temporal adverbial subordinate clauses with the manipulation of the gender feature in the participle as disambiguating information. The authors used the self-paced reading experimental paradigm with a control response. The results were in line with that predicted by the Feature Strength Hypothesis and Antecedent Position Hypothesis put forth by Carminati (2005). References  Ariel, M. (1991). The function of accessibility in a theory of grammar. Journal of Pragmatics, 16(5), 443-463. doi: 10.1016/0378-2166(91)90136-L Carminati, M. N. (2002). The processing of Italian subject pronouns. Dissertação de doutoramento, University of Massachusetts at Amherst, Amherst, MA: GLSA Publications. Carminati, M. N. (2005). Processing reﬂexes of the Feature Hierarchy (Person > Number > Gender) and implications for linguistic theory. Lingua, 115, 259–285. doi: 10.1016/j.lingua.2003.10.006 Lasnik, H. & Lohndal, T. (2017). Noam Chomsky. In Oxford Research Encyclopedia of Linguistics. doi: 10.1093/acrefore/9780199384655.013.356 Duarte, M. E. L. (2015) A perda do princípio “Evite Pronome” no Português Brasileiro. Campinas, SP: EDUNICAMP. Filiacia, F. Soracea, A., Carreiras M. (2013) Anaphoric biases of null and overt subjects in Italian and Spanish: a cross-linguistic comparison. Language, Cognition and Neuroscience, doi: 10.1080/01690965.2013.801502 Gelormini-Lezama, C., Almor, A. (2011). Repeated names, overt pronouns, and null pronouns in Spanish, Language and Cognitive Processes, 26(3), 437-454. doi: 10.1080/01690965.2010.495234 Gonçalves, A. V. G., Sousa, M. L. (2012). Ciências Da Linguagem: O Fazer Cientifico?. (1. Ed.). São Paulo, SP. Editora Mercado de letras. Grosjean, F. (1996). Living with Two Languages and Two Cultures. In I. Parasnis, Ed. Cultural and language diversity and the deaf experience. (pp. 20-37). Cambridge: Cambridge University Press. Kaiser, E., Fedele, E. (2019). Reference resolution: a psycholinguistic perspective. J. Gundel & B. Abbott, (Eds.). The Oxford Handbook of Reference. doi: 10.1093/oxfordhb/9780199687305.013.15 Lapertua, M. (2004) Sujeito nulo na aquisição: um parâmetro em mudança – sujeito preenchido na aprendizagem: a eterna tentativa de mudança. Revista do Gelne, 6(1), 141. Limberger, B., Buchweitz, A. (2012). Estudos sobre a relação entre bilinguismo e cognição: o controle inibitório e a memória de trabalho. Letrônica, 5(3), 67-87, Lucchesi, D. (2009). A realização do sujeito pronominal. In D. Lucchesi, A. Baxter, & I. Ribeiro, (Eds.). O português afro-brasileiro (pp. 165-183). Salvador, BA: EDUFBA. Presuss, E. O., Finger, I. F. (2018). A dinâmica do Processamento Bilíngue. Campinas, SP. Pontes Editoras. Veríssimo, V. (2017). A evolução do conceito de parâmetro do sujeito nulo. Entrepalavras, Fortaleza, 7, 76-90. Xavier, G. R. (2006). Português Brasileiro como Segunda Língua: Um Estudo sobre o Sujeito Nulo. Campinas, SP: EDUNICAMP.

APA, Harvard, Vancouver, ISO, and other styles

42

Weigand, Edda. "Dialogue and Artificial Intelligence." Language and Dialogue 9, no. 2 (2019): 294–315. http://dx.doi.org/10.1075/ld.00042.wei.

Full text

Abstract:

Abstract The article focuses on a few central issues of dialogic competence-in-performance which are still beyond the reach of models of Artificial Intelligence (AI). Learning machines have made an amazing step forward but still face barriers which cannot be crossed yet. Linguistics is still described at the level of Chomsky’s view of language competence. Modelling competence-in-performance requires a holistic model, such as the Mixed Game Model (Weigand 2010), which is capable of addressing the challenge of the ‘architecture of complexity’ (Simon 1962). The complex cannot be ‘the ontology of the world’ (Russell and Norwig 2016). There is no autonomous ontology, no hierarchy of concepts; it is always human beings who perceive the world. ‘Anything’, in the end, depends on the human brain.

APA, Harvard, Vancouver, ISO, and other styles

43

Sureshkumar, William, and Reghavan Rama. "Regulating a Distributed Computing Model via Chomsky Hierarchy." GSTF Journal of Mathematics, Statistics and Operations Research 3, no. 1 (2015). http://dx.doi.org/10.5176/2251-3388_3.1.59.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Yankovskiy, Vladimir. "Groups with context-free Diophantine problem." journal of Groups, complexity, cryptology Volume 13, issue 1 (August 26, 2021). http://dx.doi.org/10.46298/gcc-7347.

Full text

Abstract:

We find algebraic conditions on a group equivalent to the position of its Diophantine problem in the Chomsky Hierarchy. In particular, we prove that a finitely generated group has a context-free Diophantine problem if and only if it is finite.

APA, Harvard, Vancouver, ISO, and other styles

45

Yankovskiy, Vladimir. "Groups with context-free Diophantine problem." journal of Groups, complexity, cryptology Volume 13, issue 1 (August 26, 2021). http://dx.doi.org/10.46298/jgcc.2021.13.1.7347.

Full text

Abstract:

We find algebraic conditions on a group equivalent to the position of its Diophantine problem in the Chomsky Hierarchy. In particular, we prove that a finitely generated group has a context-free Diophantine problem if and only if it is finite.

APA, Harvard, Vancouver, ISO, and other styles

46

Lee, Shin-Jye, Ching-Hsun Tseng, and Ying-Yi Chou. "A Brief Concept of Natural Language Processing: The Chomsky Hierarchy and Hidden Markov Models." International Journal of Software & Hardware Research in Engineering 9, no. 6 (2021). http://dx.doi.org/10.26821/ijshre.9.6.2021.9614.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Peichl, Timo, and Heribert Vollmer. "Finite Automata with Generalized Acceptance Criteria." Discrete Mathematics & Theoretical Computer Science Vol. 4 no. 2 (January 1, 2001). http://dx.doi.org/10.46298/dmtcs.287.

Full text

Abstract:

International audience We examine the power of nondeterministic finite automata with acceptance of an input word defined by a leaf language, i.e., a condition on the sequence of leaves in the automaton's computation tree. We study leaf languages either taken from one of the classes of the Chomsky hierarchy, or taken from a time- or space-bounded complexity class. We contrast the obtained results with those known for leaf languages for Turing machines and Boolean circuits.

APA, Harvard, Vancouver, ISO, and other styles

48

Mishra, U. K., K. Mahalingam, and R. Rama. "Watson–Crick Jumping Finite Automata: Combination, Comparison and Closure." Computer Journal, January 4, 2021. http://dx.doi.org/10.1093/comjnl/bxaa166.

Full text

Abstract:

Abstract A new model of computation called Watson–Crick jumping finite automata was introduced by Mahalingam et al., and the authors study the computing power and closure properties of the variants of the model. There are four variants of the model: no state, 1-limited, all-final and simple Watson–Crick jumping finite automata. In this paper, we introduce a restricted version that is a combination of variants of the existing model. It becomes essential to explore the computing power and closure properties of these combinations. The combination variants are extensively compared with Chomsky hierarchy, general jumping finite automata family and among themselves. We also explore the closure properties of such restricted automata.

APA, Harvard, Vancouver, ISO, and other styles

49

Bellik, Jennifer, and Nick Kalivoda. "Automated tableau generation using SPOT (Syntax Prosody in Optimality Theory)." Linguistics Vanguard 5, no. 1 (2019). http://dx.doi.org/10.1515/lingvan-2017-0051.

Full text

Abstract:

AbstractMuch recent work on the syntax-prosody interface has been based in Optimality Theory. The typical analysis explicitly considers only a small number of candidates that could reasonably be expected to be optimal under some ranking, often without an explicit definition of GEN. Manually generating all the possible candidates, however, is prohibitively time-consuming for most input structures – the Too Many Candidates Problem. Existing software for OT uses regular expressions for automated generation and evaluation of candidates. However, regular expressions are too low in the Chomsky Hierarchy of language types to represent trees of arbitrary size, which are needed for syntax-prosody work. This paper presents a new computational tool for research in this area: Syntax-Prosody in Optimality Theory (SPOT). For a given input, SPOT generates all prosodic parses under certain assumptions about GEN, and evaluates them against all constraints in CON. This allows for in-depth comparison of the typological predictions made by different theories of GEN and CON at the syntax-prosody interface.

APA, Harvard, Vancouver, ISO, and other styles

50

Yee, Siang Gan, Wan Heng Fong, Nor Haniza Sarmin, and Sherzod Turaev. "Weighted Simple and Semi-Simple Splicing Systems." Malaysian Journal of Fundamental and Applied Sciences 10, no. 4 (2014). http://dx.doi.org/10.11113/mjfas.v10n4.324.

Full text

Abstract:

The modelling of splicing system has been introduced theoretically by Head in 1987. As time goes on, various splicing systems have been developed, such as one-sided, simple and semi-simple splicing systems. However, in the investigation on the generative power of splicing system, there are limitations on the generative power of splicing system with finite components. In order to overcome the limitation of the usual splicing system, one variant of splicing system has been introduced recently, called the weighted splicing system. In this paper, we associate weights from selected weighting spaces to the axioms of simple and semi-simple splicing systems, thus introducing weighted simple splicing system and weighted semi-simple splicing system. Some examples are presented for weighted simple and semi-simple splicing systems to illustrate their generative power. Lastly, relation of the languages generated by weighted simple and semi-simple splicing systems in the Chomsky hierarchy are also investigated.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Chomsky hierarchy'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles